Quicksort
Picks one value, the pivot, and moves smaller values to its left and bigger ones to its right. Then it does the same for each side.
- Ω(n log n)
- Θ(n log n)
- O(n²)
- O(log n)
- no
- yes
Best case: how the time grows with the list size n when the input is the easiest for this algorithm.
Average: the usual growth of time with n. n² means twice as many values take about four times as long; n log n grows much more slowly.
Worst case: the growth on the hardest input. Useful when speed must never drop.
Space: how much extra memory is needed besides the list. 1 means a few variables, n means a copy of the list.
Stable: two equal values keep their original order. Matters when sorting by one field of a record.
In place: sorts inside the list itself, with no second list.
- comparing
- moving
- pivot
- in final place
Try this: Pick a reversed list. The pivot is always the smallest or the biggest value left, so one side of every split is empty and the cost climbs towards n².
How it works
Here the pivot is the last value of the range. Going from left to right, every value that is not bigger than the pivot is swapped into the left part. Then the pivot goes between the two parts, where it stays for good. Each part is then sorted the same way.
When it is a good choice
One of the fastest ways to sort in practice, and it needs almost no extra memory. But if it keeps picking a bad pivot, for example on a list that is already sorted, it becomes slow. Real versions choose the pivot more carefully.