I find Mergesort to be much more intuitive. And better yet, it has a much better worst-case performance.
I find Mergesort to be much more intuitive. And better yet, it has a much better worst-case performance.
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.
Nope. Quicksort is much worse: time O(n^2). See [1].
[1] https://en.wikipedia.org/wiki/Quicksort#Worst-case_analysis
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/l...