Not 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 requi

Not 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...