Quick sort

Merge sort is fast, but it needs a second array as big as the input. Quick sort sorts inside the array, and many standard libraries use it for numbers.

It has one tricky step, the partition, with two pointers that walk toward each other. This lesson walks through it slowly. Then it shows the one input that makes quick sort slow, and the fix.

Read the problem

Questions to ask before you code:

• Can values repeat? Yes. Decide where values equal to the pivot go. Here they go left. Many repeats are a second trap.
• Can the input already be sorted? Ask this one every time. It is quick sort's trap (see below).
• n up to 10⁵ means the target is O(n log n), as with merge sort.

The idea: put one item in its final place

Remember it as: pick a pivot, smaller to the left, bigger to the right, repeat on each side.

1. Pick one value, the pivot. Here it is the first item.
2. Partition: move values ≤ pivot to its left and values > pivot to its right.
3. The pivot is now in its final sorted place. It never moves again.
4. Sort the left side and the right side the same way.

┌────────────────────────────────────────────┐
│                                            │
│    start      [13  46  24  52  20   9]     │
│    pivot 13     9  13 [24  52  20  46]     │
│    pivot 24     9  13  20  24 [52  46]     │
│    pivot 52     9  13  20  24  46  52      │
│                                            │
│    [ ] = a piece still to sort             │
│    no brackets = in its final place        │
│                                            │
└────────────────────────────────────────────┘

Merge sort does its work after the recursive calls (the merge). Quick sort does its work before them (the partition). Then there is nothing to combine.

Partition, step by step

Two pointers walk toward each other:

• i moves right and stops at a value that is too big for the left (> pivot).
• j moves left and stops at a value that belongs on the left (≤ pivot).
• If they have not crossed, swap those two values. Both are now on the right side.
• When they cross, swap the pivot with a[j].

The rule that makes it work, at every moment:

• everything left of i is ≤ pivot,
• everything right of j is > pivot.

When the pointers cross, j sits on the last value ≤ pivot. So that slot is where the pivot belongs.

The code

JavaPythonTypeScript

int partition(int[] a, int low, int high) {
    int pivot = a[low];
    int i = low, j = high;
    while (i < j) {
        while (i < high && a[i] <= pivot) i++;
        while (j > low && a[j] > pivot) j--;
        if (i < j) {
            int t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    int t = a[low];
    a[low] = a[j];
    a[j] = t;
    return j;
}

• The two inner loops are the pointer walks. i < high and j > low stop them at the edges of the piece.
• The swap after the loop drops the pivot into slot j. The function returns that slot.
• In Java, each swap goes through a temporary variable t. Python and TypeScript swap in one line.

JavaPythonTypeScript

void quickSort(int[] a, int low, int high) {
    if (low >= high) return;
    int p = partition(a, low, high);
    quickSort(a, low, p - 1);
    quickSort(a, p + 1, high);
}

• Base case: a piece of one item (or none) is sorted.
• The pivot at p is final, so the two calls skip it.
• The first call: TypeScript fills in low and high by default. In Java, call quickSort(a, 0, a.length - 1). In Python, call quick_sort(a, 0, len(a) - 1).

Fast on average, slow on sorted input

The usual case: O(n log n)

One partition walks its whole piece once: O(n) per level of calls. On random data, the pivot usually lands somewhere near the middle. The pieces shrink by about half, so there are about log n levels, as in merge sort.

Extra space is only the call stack: about log n frames.

The trap: sorted input

Feed it a sorted array. The first item is now the smallest, so every partition splits off nothing.

┌─────────────────────────────────────────────┐
│                                             │
│   call 1   [9 13 20 24 46 52]   6 items     │
│   call 2     [13 20 24 46 52]   5 items     │
│   call 3        [20 24 46 52]   4 items     │
│   call 4           [24 46 52]   3 items     │
│   call 5              [46 52]   2 items     │
│                                             │
│   6 + 5 + 4 + 3 + 2 = 20, about n × n / 2   │
│                                             │
└─────────────────────────────────────────────┘

This is not rare. Data is often sorted or nearly sorted already. Measured in Node.js:

On larger sorted arrays, the first-item version did not finish. The call stack ran out, at a different size in each language:

Python stops first because it allows only 1,000 nested calls by default. All three crash long before the limit of n = 10⁵.

The fix: a random pivot

Swap a random item to the front before each partition. The partition code stays the same.

JavaPythonTypeScript

void quickSort(int[] a, int low, int high) {
    if (low >= high) return;
    int r = low + (int) (Math.random() * (high - low + 1));
    int t = a[low];
    a[low] = a[r];
    a[r] = t;
    int p = partition(a, low, high);
    quickSort(a, low, p - 1);
    quickSort(a, p + 1, high);
}

• Java and TypeScript scale Math.random(), a number from 0 up to 1, to a slot from low to high.
• Python's random.randint(low, high) includes both ends, so it picks from the same slots.

The order of the input no longer matters. The worst case is still O(n²), but it now needs very bad luck. With this fix, a sorted array of 100,000 items took about 2.2 million comparisons, and the deepest call stack was about 40 calls.

One more trap: many equal values

A random pivot does not help when most values are equal. Every value is ≤ pivot, so the whole piece goes left again. 5,000 copies of the number 7 took about 12.5 million comparisons and a call stack 5,000 deep, random pivot or not.

The fix is a three-way partition: values smaller than the pivot, equal to it, and bigger. The equal group is final at once. You will build that split in the lesson "Sort 0s, 1s and 2s in one pass".

Merge sort or quick sort

Quick sort is not stable: its long swaps can jump one value past an equal one. For plain numbers that does not matter, because two 5s look the same. For records, it does.

What the built-in sort in your language uses

• Java promises stability only for objects, such as an Integer[] or a String[]. For an int[], two equal values look the same, so order does not matter.
• The JavaScript spec requires a stable sort since ECMAScript 2019, but does not name the algorithm. V8, in Chrome and Node.js, uses TimSort.

How to spot when sorting helps

In interviews you rarely write a sort. You call one, in O(n log n), and then the problem gets easy. Look for these words:

Sorting costs O(n log n). When the rest of the work is one O(n) pass, the whole answer is O(n log n), which fits n = 10⁵.

take U forwardYouTube

Read more

• Overview of quicksort on Khan Academy, partitioning with pictures
• VisuAlgo: sorting, pick quick sort and its random pivot version
• Arrays in the Java docs, the notes on Dual-Pivot Quicksort and TimSort
• Quicksort on Wikipedia, with other partition schemes and pivot choices

Next: largest elements and rotations, the first lesson of the Arrays chapter.