3 ms·
>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 belie
by 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 agoIntrosort 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).