alt Hacker NewsQuicksort is quick because it's space requirements are very far from _n_, as they are just O(log n).
A fast sorting algorithm whose space requirements are closer to n would be e.g. merge sort.
Quicksort is quick because it's space requirements are very far from _n_, as they are just O(log n).
A fast sorting algorithm whose space requirements are closer to n would be e.g. merge sort.
If you use O(log n) space you are doing IO because n items requires n memory so most of your items are sitting someplace slow.
Quicksort requires n+c space where c is a few pointers.
https://www.cs.ox.ac.uk/files/6226/H2006%20-%20Historic%20Qu...