6 ms·

How does it compare to an O(1) space version of quicksort?

• astrada 13y ago
  quicksort is not a stable sort (http://en.wikipedia.org/wiki/Stable_sort#Stability http://en.wikipedia.org/wiki/Stable_sort#Stability)
• beagle3 13y ago
  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-to-implement-quicksort-with-o1-space-complexity 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 http://www.cs.dartmouth.edu/~doug/mdmspe.pdf -
  • klmr 13y ago
    Many/most widely used “quicksort” implementations are actually introsort (in particular, `std::sort` is), and thus O(nlogn) worst case.
• anonymoushn 13y ago
  There is no O(1) space version of quicksort.