Pointer Walk

Quicksort

Pick a pivot, split around it, repeat on each side. Watch each split put one item in its final place.

AlgorithmsIntermediate10 min read

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.

  1. Pick one item. Call it the pivot

    Here it is always the last item of the section being sorted.

  2. 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.

  3. 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.

QuicksortInteractive
8
3
12
5
14
1
9
6
13
2
11
4
10
7
  • 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.
python
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.

ComparisonsWhen
TypicalAbout n log nPivots land somewhere in the middle
WorstAbout n² / 2Every 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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    8 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress