Quick sort

Prerequisites

• Recursion: a function that calls itself on a smaller input.
• Swapping two array elements.
• Big-O notation (see Complexity analysis), and ideally Merge sort.

The analogy

How it works

Start with one partition by hand

Take [5, 2, 6, 1, 4], pivot = 4. Walk left to right; every number ≤ 4 gets swapped into a growing "left zone" at the front. Guess first, then open "Check".

Finish the run

Now sort each side of [2, 1 | 4 | 5, 6] the same way.

• Left side [2, 1], pivot 1. Predict the result.
  Check

  2 > 1 is skipped, then 1 swaps to the front: [1, 2].

• Right side [5, 6], pivot 6. Predict: does anything move?
  Check

  No. 5 ≤ 6 stays in the zone and 6 stays last. Final array: [1, 2, 4, 5, 6].

The rule in plain words

Pick the last number as the pivot. Walk through the rest; swap every number ≤ pivot into the left zone. Finally, swap the pivot right after the zone.

The pivot is now final. Repeat on the part left of it and the part right of it. A part of size 0 or 1 is already sorted.

The code

Read this code after you have done one partition by hand. It will make more sense.

static void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; }
int partition(int a[], int lo, int hi) {     /* Lomuto, pivot = a[hi] */
    int pivot = a[hi], i = lo - 1;           /* a[lo..i] is the left zone */
    for (int j = lo; j < hi; j++)
        if (a[j] <= pivot) swap(&a[++i], &a[j]);
    swap(&a[i + 1], &a[hi]);                 /* pivot after the zone */
    return i + 1;
}

void quick_sort(int a[], int lo, int hi) {   /* sorts a[lo..hi] */
    if (lo >= hi) return;
    int p = partition(a, lo, hi);
    quick_sort(a, lo, p - 1);                /* a[p] is final: skip it */
    quick_sort(a, p + 1, hi);
}

graph TD
  A["5 2 6 1 4 (pivot 4)"] -->|partition| B["2 1 | 4 | 5 6"]
  B --> C["2 1 (pivot 1)"]
  B --> D["5 6 (pivot 6)"]
  C -->|partition| E["1 | 2"]
  D -->|partition| F["5 | 6"]
  E & F --> G["1 2 4 5 6"]
          

How fast is it?

With balanced pivots there are about $\log_2 n$ levels of $n$ work each, so $O(n \log n)$. With the worst pivots, the parts shrink by one:

Random pivots, or the median of the first, middle and last elements, make the bad case very unlikely.

Common mistakes

• Forgetting the final swap that puts the pivot after the left zone.
• Recursing on [lo, p] instead of [lo, p - 1], which can recurse forever on the same range.
• Using a fixed first or last pivot on data that may already be sorted.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• After a partition the pivot is final, because everything left of it is ≤ it and everything right of it is bigger.
• The average case is $O(n \log n)$ because reasonably balanced splits give about $\log_2 n$ levels of $n$ work.
• The worst case is $O(n^2)$ because a pivot that is always the min or max shrinks the problem by only one.
• It is not stable because partition swaps can jump an element over an equal one.
• Its extra space is $O(\log n)$ because the only memory it uses is the recursion stack.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is quick sort like a coach splitting players by height?
   Sample answer

   The coach picks a reference player, sends shorter players left and taller players right, and the reference player's spot is now correct. Each group then repeats the process.

2. Walk through the first partition of [5, 2, 6, 1, 4] with pivot 4.
   Sample answer

   5 is skipped, 2 joins the left zone, 6 is skipped, 1 joins the zone, then 4 swaps in after the zone: [2, 1, 4, 5, 6].

3. Why does the code recurse on p - 1 and p + 1, not on p?

   A good answer says what is special about index p.

   Sample answer

   The pivot at p is already in its final place, so there's nothing left to do there. Including it could also make a range never shrink, giving infinite recursion.

4. So what is quick sort, in one sentence?
   Sample answer

   It partitions the array around a pivot so the pivot lands in its final place, then sorts the two sides the same way.

5. Why does a sorted array make this quick sort $O(n^2)$?

   A good answer says how big the two sides are.

   Sample answer

   With the last element as pivot, the pivot is always the maximum, so one side is empty and the other has everything else. The sizes go $n-1$, $n-2$, …, adding up to $\frac{n(n-1)}{2}$.

6. What are its best, average and worst cases, and its extra space?
   Sample answer

   $O(n \log n)$ in the best and average case, $O(n^2)$ in the worst case. Extra space is the recursion stack, $O(\log n)$ on average.

7. How do you make the bad case unlikely?
   Sample answer

   Choose a random pivot, or the median of the first, middle and last elements. Then no particular input order, like sorted, can trigger the worst case on purpose.

8. Quick sort is usually fastest. Why would anyone choose merge sort or heap sort instead?
   Sample answer

   Merge sort is stable and guarantees $O(n \log n)$. Heap sort guarantees $O(n \log n)$ with $O(1)$ extra memory. Quick sort offers neither guarantee.

9. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the Lomuto index details and the stack-space discussion. I'd keep the coach analogy, one partition on a small array, "the pivot is final", and "fast on average, $O(n^2)$ with bad pivots".

External resources

• VisuAlgo: Sorting: pick "QUI" or "R-Q" (random pivot) and compare.
• GeeksforGeeks: Quick sort: an article covering Lomuto and Hoare partitioning.
• Wikipedia: Quicksort: history, pivot strategies and analysis.
• Toptal: Quick sort animation: compare it with the other sorts on different inputs.

Videos

• YouTube: quick sort as a folk dance: the AlgoRythmics video for quick sort.
• YouTube search: quicksort partition explained: pick a walkthrough of the partition step.