1) yes. 2) I think you're under a misconception that the C qsort function has anything to do with quicksort aside from a historical choice of naming...
-
-
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.