News for hackers. Stuff that matters.
Re:Writing a Faster Sorting Algorithm by tener on Tuesday January 03, 2017 @08:15AM (#13308853)
Neat algorithm, but it is largely comparing apples to oranges. std::sort is universal, ska_sort is not:

> Another problem is that I’m not sure what to do for data that I can’t sort. For example this algorithm can not sort a vector of std::sets

> Another problem is that right now there can only be one sorting behavior per type. You have to provide me with a sort key, and if you provide me with an integer, I will sort your data in increasing order. If you wanted it in decreasing order, there is currently no easy interface to do that.

Useful algorithm, but we already knew there are faster algorithms if we introduce additional requirements!

Re:Writing a Faster Sorting Algorithm by willtim on Tuesday January 03, 2017 @10:38AM (#13309794)
With some generic programming, even complex data can be radix sorted in linear time. Google the Discriminator papers of Fritz Henglein.
Re:Writing a Faster Sorting Algorithm by dancodes on Tuesday January 03, 2017 @10:33AM (#13309756)
Do you know of any resource which details these faster algorithms when given extra requirements?
Re:Writing a Faster Sorting Algorithm by martincmartin on Tuesday January 03, 2017 @10:40AM (#13309812)
Radix sort (and its variant trie sort) are the biggest ones:

https://en.wikipedia.org/wiki/Radix_sort

The O(n log n) lower bound is only for comparison based sorts. If you don't take a comparison function, but instead look at the internal structure, you can do better, but of course that depends on that internal structure and what order you want them in.