[tener]

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!

[willtim]

With some generic programming, even complex data can be radix sorted in linear time. Google the Discriminator papers of Fritz Henglein.

[eternalban]

http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl...

http://www.diku.dk/hjemmesider/ansatte/henglein/papers/hengl...

https://pdfs.semanticscholar.org/f425/7af9221ca7fe21dc84a049...

[dancodes]

Do you know of any resource which details these faster algorithms when given extra requirements?

[martincmartin]

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.