3 ms·

Doesn't quicksort have the least memory usage ?

• DSMan195276 10y ago
  Quicksort still requires O(lg n) memory because of its recursive nature. Since (lg n) is generally small, it's not that big of a deal. But with bad data, it's possible for Quicksort to degenerate to O(n) extra memory, which could be an issue (Especially for machines with little stack space). Heapsort (And thus smoothsort) are not recursive, so they require a constant amount of memory for all inputs.
  • eutectic 10y ago
    What if you always recurse into the smaller half, and use tail-recursion/looping to process the rest? Doesn't that keep the space usage bounded to O(log(n))?
    • deathanatos 10y ago
      This is correct, and is noted in the Wikipedia article's discussion of memory usage[1]. (Which I was only reading because I was erroneously thinking that quicksort was O(1) memory – I was completely forgetting stack space.) [1]: https://en.wikipedia.org/wiki/Quicksort#Space_complexity https://en.wikipedia.org/wiki/Quicksort#Space_complexity