4 ms·
Plus quicksort is a classic morass- by the time you harden it enough to deal with real world data you could have written a proper merge sort with similar averag
by jmount 14y ago
Plus quicksort is a classic morass- by the time you harden it enough to deal with real world data you could have written a proper merge sort with similar average case performance and much better worst case guarantee. My rant on quicksort: http://www.win-vector.com/blog/2008/04/sorting-in-anger/ http://www.win-vector.com/blog/2008/04/sorting-in-anger/
- gnuvince 14y agoInteresting read, thanks for linking it. When I need to write a sorting algorithm, I usually for Merge Sort, because I can never remember the exact details of swapping/partitioning of QuickSort. It seems much more natural to say "split your data in two, sort them, merge them together". And when I'm feeling damn fancy, I use an InsertSort when the size of the dataset is less than 7-8, another algorithm that I find difficult to forget (at least, the recursive definition; I usually need some paper and pencil to do the in-place version).