Quicksort can use O(log(n)) space in the worst case. Recurse into the smaller sub array first and the space will be bounded. http://www.seeingwithc.org/topic2html.html Rrenaud 18:30, 31 Dec 2004 (EST)
He calls it quicksort, but it's actually introspective sort without one more optimization. I prefer the "original" quicksort when using comparisons. I want to bring it up as a learning tool, and as such, it is important to know the original algorithm.. maybe when in the summary, we can add about how difficult it is to actually achieve the worst-case (especiall with the median-of-three method), or ways to change that.
Maybe we can file that under "Modified Quicksort".. Larry 17:16, 1 Jan 2005 (EST)
Maybe k should be max_element - min_element, and it should be noted that countsort isn't a compare-based sort since it requires (at least to my knowledge), the input to be integers. --Rrenaud 22:40, 6 Feb 2005 (EST)