I suppose this is why C++ uses introsort, which is basically a quicksort that churns for no more than O(n log n) steps before "bailing out" to a guaranteed O(n log n) algorithm like heapsort. That lets it get quicksort's in-practice-fast speeds on almost all inputs, while falling back to no worse than O(n log n) in the rare cases where quicksort would go quadratic (though it'll be worse in those rare cases, by a constant factor, than just running heapsort originally would've been).<p>edit: <a href="http://www.cs.rpi.edu/~musser/gp/introsort.ps" rel="nofollow">http://www.cs.rpi.edu/~musser/gp/introsort.ps</a>