Today while doing some reading I came across some comparison of quicksort and merge sort. Then a question struck me: what is the “best” sorting algorithm? I know I had thought of that question time and again, but I have never got down to figure it out. Well, until today.
Wikipedia has a table comparing a bunch of algorithms, that can be sorted by each property (best case, average case, worst case, memory usage and stability). However, I find that a bit of work is needed to figure out the “best”.
Set Up
The method is simple: among the many algorithms, find the ones that has the best value for the best case, plus the best value for the average case, plus the best value for the worst case and so on. The best values are as follow:
- Best case:
n - Average cases:
n log n - Worst case:
n log n - Memory usage:
1 - Stability:
Yes
Results
And… there is no algorithms that comes up with all the best values! Okay that’s to be expected, otherwise sorting algorithms would be too boring. People need to make trade-offs.
UPDATE (2015/09/13): Adrian Mejia pointed out that the table has since been updated, and now block sort is the clear winner!!!
If you can trade stability, smoothsort is the winner. If you can trade memory usage, try timsort or tree sort. If you need both stability and memory efficiency, you will have to give up on the average and worse case: use insertion sort, gnome sort, cocktail sort or bubble sort.
Why isn’t quicksort here? Or merge sort? Not sure, but my guess is that it’s some implementation details.
Questions or comments can go to Google+ :)