3 ms·
A lot of things get called 'quicksort' that are not as quick as Hoare's original algorithm. Pragmatically, it was quick compared to Von Neumann's merge sort. S
by brudgers 10y ago
A lot of things get called 'quicksort' that are not as quick as Hoare's original algorithm. Pragmatically, it was quick compared to Von Neumann's merge sort.
Sure both are time O{n log n}. Sure both are space O{n}. But merge sort is ~2n + c space and quicksort is n + c space. In the days when computers had kilobytes of memory and rooms full of tape drives, the memory efficiency of quicksort made it much quicker.
Which brings up the difference between mathematical worst case performance and engineering worst case performance. Statistically, the use of a random pivot (which was part of Hoare's paper) gives quicksort similar worst case performance to merge sort. In production with 'big data', hitting slow secondary memory such as persistent storage will dominate throughput.
- amelius 10y ago> Sure both are time O{n log n}. Nope. Quicksort is much worse: time O(n^2). See [1]. [1] https://en.wikipedia.org/wiki/Quicksort#Worst-case_analysis https://en.wikipedia.org/wiki/Quicksort#Worst-case_analysis
- brudgers 10y agoBecause it uses a randomized pivot, the worst case for Hoare's implementation has a probability on the order 1/n!. With twenty inputs, that's 1/(2.4 * 10^18). Probabalistic analysis [1] is the difference between theory and practice. Hoare knew what he was doing and it's no accident was recognized with a Turing Award. [1] https://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/lecture_notes/lect0123.pdf https://www.cs.cmu.edu/afs/cs/academic/class/15451-s07/www/l...