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 eternalban on Tuesday January 03, 2017 @10:50AM
(#13309895)
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.
> 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!