Sooo.. whats the fastest sort algorithm nowadays?

[blahblah99]

I'm familiar with shell sort, quick sort, heap sort, etc. Has there been any evolution in sort algorithms over the last 10 years or have sort algorithms reached its speed peak, assuming a random array of N elements have to be sorted and that the elements can be all strings or all numeric.

To me it seems like any of the O(n log n) are commonly used. Is there anything better or is O(n log n) the fastest it'll ever get?

 

[Cogman]

It depends on what you are sorting. If it is a list of Ints and possibly even floats, then a radix sort is still the fastest.

After that, it depends on application. For example. If you are working with slow media, then a merge sort would be the best bet. Quick sort generally works really good, but there are some cases where a heap sort will be faster.

For comparison sorts, nothing is faster then a O(n log n). However, since a radix sort isn't a comparison sort it comes to a O(k*n), where k the number of digits being processed.

merge sort is the easiest to multi-thread (though quick sort isn't too bad). Radix sorting can be multi threaded, but its a pain. You have to use MSD radix sort as opposed to the easer to write LSD radix sort.

 

[dinkumthinkum]

There is a provable worst-case lower bound on sorting in the comparison model, that is Omega(n*floor(log(n))). So if you were expecting to check back every 5 years for a better algorithm, I think you'll be disappointed.

 

[Journer]

you need more chinese people and monkeys in your box...that might help things out a bit

anyways, wouldnt the 'fastest' algorithm be totally dependent on hardware and what you are sorting?

 

[degibson]

Originally posted by: Journer

anyways, wouldnt the 'fastest' algorithm be totally dependent on hardware and what you are sorting?

No.