News for hackers. Stuff that matters.
Re:WikiSort – Fast, stable, O(1) space merge sort algorithm by apples2apples on Saturday March 15, 2014 @08:19AM (#7404402)
How does it compare to an O(1) space version of quicksort?
Re:WikiSort – Fast, stable, O(1) space merge sort algorithm by astrada on Saturday March 15, 2014 @08:30AM (#7404427)
Re:WikiSort – Fast, stable, O(1) space merge sort algorithm by beagle3 on Saturday March 15, 2014 @11:14AM (#7404821)
Quicksort is worst case O(n^2) time, unless you incorporate something like Quickselect for your pivot (which no one ever does, because it makes it relatively complicated. Have you ever seen an O(n log n) guaranteed quicksort implemented? I haven't - best I've seen is median-of-3 or median-of-5 pivots - or randomized). Furthermore, I've never seen an O(1) space version of quicksort and I'm not sure one can exist -- see, e.g. http://stackoverflow.com/questions/11455242/is-it-possible-t...

The meaningful comparison would actually be to Heapsort, which is in-place, O(1) space, and NOT stable - though much, much, simpler.

ADDED:

Anyone who uses quicksort should read this gem from Doug McIlroy, which elicits an O(n^2) behaviour from most quicksort implementations: http://www.cs.dartmouth.edu/~doug/mdmspe.pdf -

Re:WikiSort – Fast, stable, O(1) space merge sort algorithm by klmr on Saturday March 15, 2014 @01:25PM (#7405272)
Many/most widely used “quicksort” implementations are actually introsort (in particular, `std::sort` is), and thus O(nlogn) worst case.
Re:WikiSort – Fast, stable, O(1) space merge sort algorithm by anonymoushn on Saturday March 15, 2014 @12:33PM (#7405064)
There is no O(1) space version of quicksort.