qsort is a function to perform comparison sorts that necessarily succeeds (has no interface for failure) and as such needs to be O(1) or effectively O(1) space. It should (QoI) also be efficient independent of input.
-
-
-
Quicksort can meet effective O(1) space (log n is effectively a constant 32 or 64) but can't be made O(n log n) time without really bad constant, and O(n²) is not nice.
-
Real-world quicksorts aiming to be safe against all inputs are introsorts (intro=introspective) -- they measure for bad-case pivoting & switch to heapsort if they detect it.
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.