3 ms·

Quicksort is O(log n) space, not O(1).

• nightcracker 11y ago
  And if you're implementing pure Quicksort you have to make sure to recurse on the smaller partition first, otherwise you're using O(n) space in the worst case. You don't have to do this if you're already using a hybrid sort to prevent Quicksort's worst case, like introsort or (shameless self promotion) pdqsort (https://github.com/orlp/pdqsort https://github.com/orlp/pdqsort).
  • sjolsen 11y ago
    >you have to make sure to recurse on the smaller partition first, otherwise you're using O(n) space in the worst case I haven't run the math, but I don't believe introsort fixes this. It's a constant-factor optimization.
    • nightcracker 11y ago
      Introsort switches to heapsort if the recursion depth becomes too big to limit runtime to O(n log n), which indirectly also limits space to O(log n).