Quick Sort, Step by Step

Quick sort is merge sort inverted. Merge sort splits trivially and does all the work combining; quick sort does all the work splitting and nothing at all on the way back up.

Choose a value from the array, called the pivot. Rearrange the array so everything smaller than the pivot sits to its left and everything larger sits to its right. The pivot is now exactly where it belongs in the final sorted array, and it never moves again. Then repeat on the left part and the right part.

There's no merge step. Once every element has been a pivot, or has landed in a range of size one, the array is sorted.

Tracing the partition

Partitioning is the whole algorithm, so it's worth walking through in full. The scheme below is Lomuto's, which takes the last element as the pivot.

Take this array, with 6 as the pivot:

[7, 2, 9, 4, 3, 7, 6]      pivot = 6 (the last element)

Two indices do the work, and understanding what each one means is the key to the whole thing:

For each element the rule is: if a[j] is smaller than the pivot, grow the smaller region by one and swap this element into it. Otherwise, do nothing and move on.

Watch the pointers do exactly that below, live, on this same array.

Step it and follow the highlighted pseudocode line.

Once the scan finishes, everything smaller than the pivot sits to the left of i, everything at least as large sits to the right, and the pivot is still parked at the end. One final swap puts it in place: exchange the pivot with position i + 1.

[2, 4, 3, 7, 9, 7, 6]      swap positions 3 and 6
[2, 4, 3, 6, 9, 7, 7]
          ^
       pivot, now at index 3 and permanently in place

Position 3 is correct in the final sorted array, and nothing will ever move it again. Everything to its left is smaller; everything to its right is larger. Those two sides can now be sorted independently, and neither can affect the other.

Each time a bar turns green in the widget above, a pivot has just landed. Unlike merge sort, where nothing is final until the very end, quick sort finishes elements one at a time as it goes.

The invariant

What makes the trace above easy to follow is that one statement is true before and after every single iteration:

a[low .. i]        all values < pivot
a[i+1 .. j-1]      all values >= pivot
a[j .. high-1]     not yet examined
a[high]            the pivot

That's the invariant. When the loop ends, j has reached the pivot, so the "not yet examined" region is empty and the array is split into exactly two parts plus the pivot. Swapping the pivot to i+1 drops it precisely on the boundary.

If you ever need to reconstruct this algorithm from memory, reconstruct the invariant first. The code follows from it.

The recursion

After partitioning our example, we're left with [2, 4, 3] and [9, 7, 7] on either side of the pivot at index 3. Quick sort calls itself on each, excluding the pivot. Step through the whole thing below and watch the same partition trick happen again inside each side:

The tree makes something easy to see that's easy to miss in code: a base case doesn't always mean an empty range. [2] and [4] each get their own call and immediately return, single elements with nowhere left to partition. That's the recursion actually bottoming out, one leaf at a time, not one big merge at the end.

Note that the pivot's index is excluded from both recursive calls. Including it would be a correctness bug in the making, and in the worst case, an infinite loop: a range that never shrinks.

The worst case

Partitioning is O(n), and there are, on a good day, log n levels of recursion, giving O(n log n). But that depends entirely on the pivot splitting the array somewhere near the middle.

Suppose the pivot is always the largest remaining value. Then everything goes to its left, the right side is empty, and the next call gets a range only one element shorter. That's n levels of recursion instead of log n, and O(n²) total.

With last-element pivoting, that's exactly what already-sorted input does: the last element is the largest every time. The most natural-looking implementation has its worst case on the most natural-looking data, which is a genuinely nasty trap.

Set the input to "already sorted" below and compare quick sort's comparison count against merge sort's.

Watch A's comparison count blow past B's.

That last case matters more than it sounds, since it's common in practice. A two-way partition on an array where every value is identical splits off nothing and runs in O(n squared), while a three-way partition finishes that same array in O(n). It's the Dutch national flag problem, covered later in this section.

The algorithm as a flowchart

As with merge sort, a flowchart can't express recursion, so this is one call with the recursive steps drawn as ordinary boxes.

Partition is a plain loop, and it maps onto a flowchart exactly. Compare it against the trace above: the decision box is the a[j] < pivot test, and the dashed arrow is the j = j + 1 loop.

Against merge sort

In practice quick sort usually wins on wall-clock time despite the worse worst case, since partitioning is a tight linear scan with excellent cache behavior, and it needs no extra buffer. That's why it's the default for primitives in most standard libraries, with the safeguards above bolted on.

In code

function quickSort(a, low = 0, high = a.length - 1) {
  if (low >= high) return a;         // 0 or 1 elements: already sorted

  const p = partition(a, low, high);
  quickSort(a, low, p - 1);          // p is excluded: it is already final
  quickSort(a, p + 1, high);
  return a;
}

function partition(a, low, high) {
  const pivot = a[high];
  let i = low - 1;                   // end of the "smaller" region, empty so far

  for (let j = low; j < high; j++) {
    if (a[j] < pivot) {
      i++;
      [a[i], a[j]] = [a[j], a[i]];   // grow the region and move a[j] into it
    }
  }

  [a[i + 1], a[high]] = [a[high], a[i + 1]];   // pivot onto the boundary
  return i + 1;
}

Check yourself