Sort by splitting
Sorting a hundred exam papers by score, you would probably not compare every paper with every other. A natural trick is to pick a score, say 60, and make two piles: below 60 and above 60. Neither pile is sorted, but no paper will ever need to cross from one pile to the other. Now do the same within each pile.
That is quicksort. It is one of the most widely used sorting algorithms, and the idea fits in three steps.
Pick one item. Call it the pivot
Here it is always the last item of the section being sorted.
Partition: move smaller items to its left, larger to its right
Afterwards the pivot is in its final, correct position. It will never move again.
Do the same to the left part and to the right part
Each is a smaller sorting problem. A part with one item or none is already sorted.
- pivot
- being compared
- smaller than the pivot
- in its final place
- waiting for its turn
Start. Fourteen bars in a jumble. Quicksort picks one bar, the pivot, and splits the rest into smaller and larger.
- Comparisons
- 0
- Swaps
- 0
- In final place
- 0 / 14
How partitioning works
Partitioning is the whole algorithm. It makes one pass over the section, keeping a growing group of "smaller than the pivot" items at the left.
- A boundary marks the end of that group.
- A scanning marker looks at each item in turn.
- If the item is smaller than the pivot, swap it to the boundary and move the boundary one step.
- At the end, swap the pivot to the boundary. Smaller on the left, larger on the right.
def quicksort(items, low, high):
if low >= high:
return # 0 or 1 items: already sorted
pivot = items[high]
boundary = low
for scan in range(low, high):
if items[scan] < pivot:
items[boundary], items[scan] = items[scan], items[boundary]
boundary += 1
items[boundary], items[high] = items[high], items[boundary] # pivot into place
quicksort(items, low, boundary - 1)
quicksort(items, boundary + 1, high)Everything happens inside the original array by swapping. No second array is needed.
How fast is it
One partition looks at every item in its section once. What matters is how evenly the pivot splits things.
Example
A good pivot and a bad pivot
Good: the pivot lands near the middle. Each level of splitting halves the sections, so there are about log₂ n levels, and each level does about n comparisons in total. That is n log n: for a million items, roughly 20 million comparisons.
Bad: the pivot is the smallest or largest item every time. One side is empty and the other has everything else. Now there are n levels, not log n, and the total is about n² / 2: for a million items, 500 billion comparisons.
The bad case is not exotic. With "always pick the last item" as the rule, an already sorted array triggers it: the last item is always the largest.
| Comparisons | When | |
|---|---|---|
| Typical | About n log n | Pivots land somewhere in the middle |
| Worst | About n² / 2 | Every pivot is the smallest or largest in its section |
Picking a better pivot
Real implementations do not use the last item.
- A random item. No particular input is bad any more. You would need to be unlucky on almost every pick.
- Median of three. Look at the first, middle and last items and use the middle value of those. Sorted and reversed inputs become the best case.
Good at
- Very fast in practice: tight loops that work on neighbouring memory
- Sorts in place, with no second array
Where it bites
- A poor pivot rule gives n² behaviour on common inputs
- Not stable: equal items may change their relative order
Key takeaways
- Quicksort picks a pivot, moves smaller items left and larger items right, then repeats on each side.
- After a partition the pivot is in its final place.
- Even splits give about n log n comparisons. Lopsided splits give about n².
- Using the last item as the pivot makes sorted input the worst case. Random or median-of-three pivots avoid that.
- It sorts inside the array, by swapping.