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?
[ Parent
| on HN ]
Re:WikiSort – Fast, stable, O(1) space merge sort algorithm
by astrada on Saturday March 15, 2014 @08:30AM
(#7404427)
quicksort is not a stable sort (http://en.wikipedia.org/wiki/Stable_sort#Stability)
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.