>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.
I haven't run the math, but I don't believe introsort fixes this. It's a constant-factor optimization.