Re:Pattern-defeating quicksort
by beagle3 on Friday June 30, 2017 @04:21AM
(#14669320)
There's actually 3:
Quick sort (unstable, n^2 worst case, in place, heapsort (unstable, n log n worst case, in place) and merge sort (stable, n log n worst case, not in place)
There are variants of each that trade one thing for another (in placeness for stability, constants for worst case), but these are the three efficient comparison sort archetypes.
Of these, quicksort and heap sort can do top-k which is often useful; and heapsort alone can do streaming top-k.
Quick sort (unstable, n^2 worst case, in place, heapsort (unstable, n log n worst case, in place) and merge sort (stable, n log n worst case, not in place)
There are variants of each that trade one thing for another (in placeness for stability, constants for worst case), but these are the three efficient comparison sort archetypes.
Of these, quicksort and heap sort can do top-k which is often useful; and heapsort alone can do streaming top-k.