3 ms·
Not true in general, however IIRC it is the case if you want optimal (i.e. n log n) time complexity.
by ThreeFx 7y ago
Not true in general, however IIRC it is the case if you want optimal (i.e. n log n) time complexity.
- beagle3 7y agoNot even in that case. Heapsort guarantees worst case n log n, and so does quicksort if you use an O(n) median selecting algorithm. Stable sorts often do require that, (mergesort is usually stabble, heapsort and quicksort are inherently not), but even that's not required - there is a completely in-place variant of merge sort that only requires O(log n) space for stack (like quicksort; heapsort is O(1)). See e.g. https://xinok.wordpress.com/2014/08/17/in-place-merge-sort-demystified-2/ https://xinok.wordpress.com/2014/08/17/in-place-merge-sort-d...
- saagarjha 7y agoApparently there is a O(n log n) time, O(1) space, stable sort: https://en.wikipedia.org/wiki/Block_sort https://en.wikipedia.org/wiki/Block_sort