Quicksort

A photographer wants a class of children lined up by height. She does not compare everyone with everyone. She picks one child, Sam, and says: "Shorter than Sam, stand on his left. Taller, on his right." Nobody on the left is sorted yet, nobody on the right is sorted yet, but Sam is now standing exactly where he belongs in the final line.

Then she does the same thing with the group on the left, and the group on the right. Each round puts at least one more child in their final place, and the groups keep shrinking. That is quicksort.

#The idea: partition around a pivot

Quicksort has three steps:

1. Pick a pivot, one item from the range.
2. Partition: rearrange the range so every item smaller than the pivot comes before it and every other item comes after it. The pivot lands in its final position.
3. Recurse on the part before the pivot and the part after it.

Compare it with merge sort. Merge sort splits without looking at the values, then does its real work when merging. Quicksort does its real work while splitting, and then there is nothing to combine: once both sides are sorted, the whole range is sorted. It also sorts in place, inside the original array.

#Partitioning, traced

The partition step is the heart of quicksort, so trace it carefully. This version uses the last item as the pivot. A boundary b marks where the next small item should go: everything left of b is smaller than the pivot. Pointer j scans the range once.

pivot = a[hi]b = lofor j from lo to hi - 1:  if a[j] < pivot:    swap a[b] and a[j]    b = b + 1swap a[b] and a[hi]return b

#The code

The partition below is the one you just traced, with one addition: it first picks a random item and swaps it to the end, so the pivot is random instead of always the last item. The next section explains why.

function quickSort(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return a; // 0 or 1 items: sorted
  const p = partition(a, lo, hi);
  quickSort(a, lo, p - 1);  // the pivot at p is already final
  quickSort(a, p + 1, hi);
  return a;
}
 
function partition(a, lo, hi) {
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [a[r], a[hi]] = [a[hi], a[r]]; // random pivot, moved to the end
  const pivot = a[hi];
  let b = lo; // a[lo..b-1] holds items smaller than the pivot
  for (let j = lo; j < hi; j++) {
    if (a[j] < pivot) {
      [a[b], a[j]] = [a[j], a[b]];
      b++;
    }
  }
  [a[b], a[hi]] = [a[hi], a[b]]; // pivot into its final slot
  return b;
}
 
quickSort([7, 2, 9, 4, 1, 6]); // [1, 2, 4, 6, 7, 9]

import random
 
def quick_sort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:  # 0 or 1 items: sorted
        return a
    p = partition(a, lo, hi)
    quick_sort(a, lo, p - 1)  # the pivot at p is already final
    quick_sort(a, p + 1, hi)
    return a
 
def partition(a, lo, hi):
    r = random.randint(lo, hi)
    a[r], a[hi] = a[hi], a[r]  # random pivot, moved to the end
    pivot = a[hi]
    b = lo  # a[lo..b-1] holds items smaller than the pivot
    for j in range(lo, hi):
        if a[j] < pivot:
            a[b], a[j] = a[j], a[b]
            b += 1
    a[b], a[hi] = a[hi], a[b]  # pivot into its final slot
    return b
 
quick_sort([7, 2, 9, 4, 1, 6])  # [1, 2, 4, 6, 7, 9]

#Good pivots and bad pivots

Partitioning a range of n items costs O(n): one scan. What matters is how evenly the pivot splits the range.

If the pivot lands near the middle every time, each level halves the work, just like merge sort. There are about log n levels with O(n) work each, so the total is O(n log n).

Now take an array that is already sorted and always use the last item as the pivot. The pivot is the biggest item, so the "smaller" side gets everything else and the "bigger" side is empty. Each level removes just one item. That is n + (n − 1) + … + 1 steps, which is O(n²), and the recursion goes n calls deep.

A random pivot fixes this. A sorted or reversed input can no longer force bad pivots, because the choice is made fresh every run. On a large array the chance of hitting the worst case is tiny, and the expected cost is O(n log n) for any input of distinct items. Many equal items are a separate problem, covered in the mistakes below.

Quicksort is not stable. The swaps in the partition throw items over each other: in the trace, 7 was thrown from slot 0 to slot 1, then to slot 3, then to slot 5. If two items had the same key, nothing would keep them in their original order.

#Common mistakes

#Check yourself

#What to practise next

Partition [5, 9, 2, 7, 3] by hand around its last item, 3: you should get [2, 3, 5, 7, 9] with the pivot at index 1. Then read Heap Sort, which guarantees O(n log n) in place, with no bad inputs at all.