Quick sort and the bad pivot in Java

Problem

The sorted price list freezes

The shop sorts its 100,000 products with quick sort: with a shuffled catalogue that is 2,136,015 comparisons, and the page opens at once. Then the supplier starts sending its price list already sorted by price. The same "Sort by price" button thinks for a long time and stops with an error:

int[] prices = catalog(100000);
Arrays.sort(prices);
Thread worker = new Thread(null, () -> {
    try {
        quickSort(prices, 0, prices.length - 1);
        System.out.println("Sorted");
    } catch (StackOverflowError e) {
        System.out.println("Out of stack: " + e.getClass().getSimpleName());
    }
}, "sort", 1024 * 1024);
worker.start();
worker.join();

Out of stack: StackOverflowError

The input is not bigger, only sorted. A sorted input should be the easiest, and here it is the hardest. To see why, first look at how quick sort works.

The idea

Pivot and partition

Merge sort splits the list into two halves without looking at the prices, and all the work is in the merging. Quick sort does the opposite: the work is in the splitting, and there is no merging. It is still divide and conquer, as in merge sort.

Pick one price as the pivot. Here it is the first price of the part.
Partition: the prices smaller than the pivot go to the left, the rest to the right, and the pivot lands between them. That is also its final place.
Sort the left and the right part with the same method. A part with one price, or an empty one, is already sorted: that is the base case of the recursion.

Partitioning swaps prices in the same array, with no copies. That is why quick sort does not need O(n) extra memory like merge sort.

See it

Partitioning step by step

Here the partition is Lomuto's: j walks over the prices one by one, and i marks the end of the left zone, where the prices below the pivot are. Every smaller price joins the zone with one swap. At the end the pivot swaps with prices[i] and lands in its place:

static int partition(int[] prices, int lo, int hi) {
    int pivot = prices[lo];
    int i = lo;
    for (int j = lo + 1; j <= hi; j++) {
        if (prices[j] < pivot) {
            i++;
            swap(prices, i, j);
        }
    }
    swap(prices, lo, i);
    return i;
}

static void swap(int[] prices, int a, int b) {
    int tmp = prices[a];
    prices[a] = prices[b];
    prices[b] = tmp;
}

Step by step, in words

The pivot is the first price, 45. i = 0 marks the end of the left zone, the prices below 45. It is still empty.
j = 1: 80 < 45? No. 80 stays on the right, i does not move.
j = 2: 20 < 45? Yes. i becomes 1 and 20 swaps places with 80: the left zone grows.
j = 3: 65 < 45? No. 65 stays on the right, i does not move.
j = 4: 10 < 45? Yes. i becomes 2 and 10 swaps places with 80: the left zone grows.
j = 5: 90 < 45? No. 90 stays on the right, i does not move.
j = 6: 30 < 45? Yes. i becomes 3 and 30 swaps places with 65: the left zone grows.
j = 7: 55 < 45? No. 55 stays on the right, i does not move.
j has reached the end: 7 comparisons for 8 prices, n − 1. The pivot swaps with prices[i] = 30 and lands at index 3.
On the left 30, 20, 10, all below 45; on the right 80, 90, 65, 55. 45 is in its final place, and the two parts are sorted separately, in the same array, with no extra memory.

int[] prices = {45, 80, 20, 65, 10, 90, 30, 55};
int p = partition(prices, 0, prices.length - 1);
System.out.println(Arrays.toString(prices) + ", p = " + p);

[30, 20, 10, 45, 80, 90, 65, 55], p = 3

partition returns where the pivot landed, p = 3. There are n − 1 comparisons: every price except the pivot is compared with it exactly once.

Java has no one-line swap of two array slots, so swap is a separate method.

See it

The whole quick sort

quickSort partitions the part from lo to hi and calls itself for both sides of the pivot. The pivot itself is already in place and goes into neither:

static void quickSort(int[] prices, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int p = partition(prices, lo, hi);
    quickSort(prices, lo, p - 1);
    quickSort(prices, p + 1, hi);
}

int[] prices = {45, 80, 20, 65, 10, 90, 30, 55};
System.out.println("Before: " + Arrays.toString(prices));
quickSort(prices, 0, prices.length - 1);
System.out.println("After: " + Arrays.toString(prices));

Before: [45, 80, 20, 65, 10, 90, 30, 55]
After: [10, 20, 30, 45, 55, 65, 80, 90]

The idea

n · log n on average, sometimes n²

What quick sort costs depends on the pivot.

A good pivot is somewhere near the middle. The two parts are about half each, and as in merge sort there are about log₂ n levels. On each level the partitions together pass over all n prices once: about n · log₂ n in total. With randomly shuffled prices the first price is random, so that is the average case.
A bad pivot is the smallest (or the largest) price in the part. The left part is empty, and the right part loses only the pivot. There are n levels and (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 comparisons. That is O(n²), as much as the simple sorts.

With sorted input the first price of every part is the smallest. So the easiest input becomes the worst case:

static void quickSort(int[] prices, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int p = partition(prices, lo, hi);
    quickSort(prices, lo, p - 1);
    quickSort(prices, p + 1, hi);
}

static void quickSort(int[] prices, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int k = RANDOM.nextInt(lo, hi + 1);
    swap(prices, lo, k);
    int p = partition(prices, lo, hi);
    quickSort(prices, lo, p - 1);
    quickSort(prices, p + 1, hi);
}

Step by step, in words

The price list is already sorted, 7 to 80. The pivot is the first price of each part.
The pivot 7 is the smallest price: 7 comparisons and nothing goes to the left. The left part is empty, the right part has 7 prices.
The same on every level: the pivot is the smallest again, and the part loses only one price. Each level is one more nested call.
8 levels and 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 comparisons, n(n − 1)/2. With 100,000 prices: 4,999,950,000 comparisons and 100,000 nested calls, more than the stack holds.
The fix: before partitioning, swap a random price of the part to the front. The rest of the code is the same.
One possible run on the same sorted list. A random pivot is usually somewhere in the middle, so both parts get prices.
5 levels instead of 8 and 17 comparisons instead of 28. Another run would differ a little, but the order of the input no longer matters: about n · log₂ n on average.

Try it

Predict the output

Five prices, and the pivot is the first one, 50. What does the program print?

static int partition(int[] prices, int lo, int hi) {
    int pivot = prices[lo];
    int i = lo;
    for (int j = lo + 1; j <= hi; j++) {
        if (prices[j] < pivot) {
            i++;
            swap(prices, i, j);
        }
    }
    swap(prices, lo, i);
    return i;
}

static void swap(int[] prices, int a, int b) {
    int tmp = prices[a];
    prices[a] = prices[b];
    prices[b] = tmp;
}

int[] prices = {50, 70, 20, 90, 40};
int p = partition(prices, 0, prices.length - 1);
System.out.println(Arrays.toString(prices) + ", p = " + p);

Answer

[40, 20, 50, 90, 70], p = 2

[40, 20, 50, 90, 70], p = 0

[20, 40, 50, 70, 90], p = 2

See it

Measure it: the first pivot and a random pivot

Run quick sort on a shuffled and on a sorted catalogue. The count is of comparisons with the pivot. The first pivot on 100,000 sorted prices is not really run: Bench estimates it from the curve.

Quick sort, first pivot, shuffled prices O(n log n)
Quick sort, first pivot, sorted prices O(n²)
Quick sort, random pivot, sorted prices O(n log n)

Algorithm	n = 10	n = 1,000	n = 10,000	n = 100,000
Quick sort, first pivot, shuffled prices	35	10,591	151,493	2,136,015
Quick sort, first pivot, sorted prices	45	499,500	49,995,000	≈ 4,999,500,000
Quick sort, random pivot, sorted prices	21	10,576	153,725	2,316,280

The code runs in your browser, in JavaScript. The number of operations is the same in every language, because the algorithm is the same. The time depends on the machine, so it is only for comparison. “≈” is an estimate from the curve: we do not run an n that big, so the page does not freeze.

static void quickSort(int[] prices, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int k = RANDOM.nextInt(lo, hi + 1);
    swap(prices, lo, k);
    int p = partition(prices, lo, hi);
    quickSort(prices, lo, p - 1);
    quickSort(prices, p + 1, hi);
}

On a shuffled catalogue of 1000 prices the first pivot makes 10,591 comparisons. On the same catalogue, sorted, it makes 499,500, exactly 1000 · 999 / 2. A random pivot on the sorted catalogue: 10,576, almost as many as on the shuffled one. With 100,000 prices the random pivot makes 2,316,280 comparisons, and the first pivot would make n(n − 1)/2 = 4,999,950,000 (Bench estimates about 5 billion from the curve).

More precisely, if you are curious

The same numbers in your language. The catalogue and the random positions come from a small seeded generator, so they are the same on every run, in every language and in Bench. This is the final version from the lesson (with recursion into the smaller part, see below), and it also prints how deep the stack got:

static long comparisons = 0;
static long seed = 0;
static int deepest = 0;

static int[] catalog(int n) {
    int[] prices = new int[n];
    long x = 2026;
    for (int k = 0; k < n; k++) {
        x = x * 48271 % 2147483647;
        prices[k] = 1 + (int) (x % 10000);
    }
    return prices;
}

static void quickSort(int[] prices, int lo, int hi, boolean random, int depth) {
    deepest = Math.max(deepest, depth);
    while (lo < hi) {
        if (random) {
            seed = seed * 48271 % 2147483647;
            swap(prices, lo, lo + (int) (seed % (hi - lo + 1)));
        }
        int p = partition(prices, lo, hi);
        if (p - lo < hi - p) {
            quickSort(prices, lo, p - 1, random, depth + 1);
            lo = p + 1;
        } else {
            quickSort(prices, p + 1, hi, random, depth + 1);
            hi = p - 1;
        }
    }
}

static int partition(int[] prices, int lo, int hi) {
    int pivot = prices[lo];
    int i = lo;
    for (int j = lo + 1; j <= hi; j++) {
        comparisons++;
        if (prices[j] < pivot) {
            i++;
            swap(prices, i, j);
        }
    }
    swap(prices, lo, i);
    return i;
}

static void swap(int[] prices, int a, int b) {
    int tmp = prices[a];
    prices[a] = prices[b];
    prices[b] = tmp;
}

String[] labels = {"first pivot, shuffled", "first pivot, shuffled", "first pivot, sorted", "random pivot, sorted", "random pivot, sorted"};
int[] sizes = {1000, 100000, 1000, 1000, 100000};
boolean[] sorted = {false, false, true, true, true};
boolean[] random = {false, false, false, true, true};
for (int r = 0; r < sizes.length; r++) {
    int[] prices = catalog(sizes[r]);
    if (sorted[r]) {
        Arrays.sort(prices);
    }
    comparisons = 0;
    seed = 12345;
    deepest = 0;
    quickSort(prices, 0, prices.length - 1, random[r], 1);
    System.out.println(labels[r] + ", n = " + sizes[r] + ": " + comparisons + " comparisons, depth " + deepest);
}

first pivot, shuffled, n = 1000: 10591 comparisons, depth 7
first pivot, shuffled, n = 100000: 2136015 comparisons, depth 11
first pivot, sorted, n = 1000: 499500 comparisons, depth 2
random pivot, sorted, n = 1000: 10576 comparisons, depth 7
random pivot, sorted, n = 100000: 2316280 comparisons, depth 11

Merge sort makes 1,536,292 comparisons on the same 100,000 prices, fewer than quick sort. Even so, quick sort is often faster in practice: it swaps prices in the same array, with no copies, and reads memory in order.

The idea

Why the stack runs out

Every call of quickSort stays on the call stack until it returns. With a bad pivot the right part is only one price smaller, so the calls nest one inside the other: n levels for n prices. The stack is limited, often about 1 MB, and with 100,000 nested calls it runs out.

Java throws StackOverflowError. It is an Error, not an Exception: it can be caught, but it usually means a bug in the program. Here the sort runs in a thread with a 1 MB stack (the fourth argument of new Thread), so that it behaves the same on every machine.

Separate from the stack is the time: n(n − 1)/2 comparisons. With 100,000 prices that is about 5 billion, which is why the button "thinks" before it fails.

The idea

Three fixes

A random pivot. Before partitioning, a random price of the part moves to the front and becomes the pivot. Then no input is bad on purpose: sorted, reversed and shuffled all give about n · log₂ n on average. The worst case still exists, but its probability is negligible: on every level the random price would have to be exactly the smallest or the largest in the part.

static void quickSort(int[] prices, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int k = RANDOM.nextInt(lo, hi + 1);
    swap(prices, lo, k);
    int p = partition(prices, lo, hi);
    quickSort(prices, lo, p - 1);
    quickSort(prices, p + 1, hi);
}

Median of three. Instead of a random price you take the middle one by value of the first, the middle-by-position and the last price. With sorted input that is exactly the middle. This fix is the exercise at the end of the lesson.

Recursion into the smaller part. The call is only for the smaller of the two parts, and the larger one stays for the loop: lo or hi moves and the loop partitions it again. The smaller part is at most half, so the stack is at most log₂ n levels with any pivot: up to 17 for 100,000 prices (the counting program gets to 11). The comparisons do not go down, so this fix goes together with the random pivot:

static void quickSort(int[] prices, int lo, int hi) {
    while (lo < hi) {
        int k = RANDOM.nextInt(lo, hi + 1);
        swap(prices, lo, k);
        int p = partition(prices, lo, hi);
        if (p - lo < hi - p) {
            quickSort(prices, lo, p - 1);
            lo = p + 1;
        } else {
            quickSort(prices, p + 1, hi);
            hi = p - 1;
        }
    }
}

int[] prices = catalog(100000);
Arrays.sort(prices);
quickSort(prices, 0, prices.length - 1);
int[] check = prices.clone();
Arrays.sort(check);
System.out.println("Sorted: " + Arrays.equals(prices, check));

Sorted: true

Try it

Find the bug

The eight prices come out almost sorted:

int[] prices = {45, 80, 20, 65, 10, 90, 30, 55};
System.out.println("Before: " + Arrays.toString(prices));
quickSort(prices, 0, prices.length - 1);
System.out.println("After: " + Arrays.toString(prices));

Before: [45, 80, 20, 65, 10, 90, 30, 55]
After: [20, 30, 10, 45, 65, 80, 90, 55]

This is the program's partition. Which line has the bug?

Pick the line with the bug.

Try it

Fill in the blank

The recursion is into the smaller, left part. What is the new value of lo, so that the loop goes on with the right part?

static void quickSort(int[] prices, int lo, int hi) {
    while (lo < hi) {
        int k = RANDOM.nextInt(lo, hi + 1);
        swap(prices, lo, k);
        int p = partition(prices, lo, hi);
        if (p - lo < hi - p) {
            quickSort(prices, lo, p - 1);
            lo = ;
        } else {
            quickSort(prices, p + 1, hi);
            hi = p - 1;
        }
    }
}

Exercise

Median of three

Solve it in your editor.

Median of three. Write median(prices, lo, hi), which looks at three prices: at lo, at the middle lo + (hi - lo) / 2 and at hi, and returns the position of the middle one by value. In quickSort (the plain recursion from the lesson), swap that price with prices[lo] before partitioning. Count the comparisons with the pivot in partition on the sorted catalogue from the lesson (catalog from the counting program, then sorted) with 1000 and with 100,000 prices.

median of three, sorted, n = 1000: 8005 comparisons
median of three, sorted, n = 100000: 1773717 comparisons

Compare with the first pivot: 499,500 comparisons for 1000 sorted prices, and with 100,000 the stack runs out.

More tasks

A reversed price list. Pass the catalogue sorted from the most expensive to the cheapest. How many comparisons does the first pivot make? And the median of three?
Equal prices. Pass 1000 equal prices. How many comparisons does Lomuto's partition make, and why? (Hint: nothing is strictly smaller than the pivot.)
Most expensive first. Change one character in partition so that the list comes out from the most expensive to the cheapest.

More precisely

Quick sort inside the built-in sort

Quick sort was invented by Tony Hoare in 1959, and it is still at the heart of the built-in sort of many languages, but not in its pure form: each one adds guards against the bad pivot.

More precisely, if you are curious

Lomuto and Hoare. The partition here is Lomuto's: it is easy to read, but it swaps more. Hoare's partition, the original one, runs two pointers from both ends towards each other and swaps only pairs of prices that are on the wrong side. It makes about three times fewer swaps and copes better with equal prices, but the pivot does not necessarily land in its final place, and the code is easier to get wrong.

Equal prices. With many equal prices Lomuto still gives bad parts: everything equal to the pivot goes to the right. A three-way partition makes three zones: smaller, equal and larger. The equal ones are done and do not go into the recursion.

The built-in sort. In Java, Arrays.sort for int[] and the other primitive arrays is a quick sort with two pivots (dual-pivot quicksort): three parts at once, and insertion sort for small parts. For arrays of objects and for List.sort Java uses TimSort, because there the sort has to be stable.

Quick sort is not stable: a swap can jump over an equal price, and equal products change their order. What that means and when it matters is in the lesson Stable sorting.

Test

Check yourself

1. What does partitioning around a pivot do?It splits the array into two exactly equal partsIt puts the smaller prices to the left of the pivot and the rest to the right; the pivot lands in its final placeIt sorts both halves of the array

2. The pivot is the first price. Which input is the worst case?A randomly shuffled price listA price list with all prices differentA price list that is already sorted

3. Why does the plain quick sort fail with StackOverflowError (RecursionError, RangeError) on 100,000 sorted prices?The array is too big for memoryThe recursion never reaches the base caseEvery level is one more nested call, and there are 100,000 levels

4. The recursion goes only into the smaller part, and the larger part is handled by a loop. What does that buy?The stack is at most log₂ n levels deep, whatever the pivotQuick sort becomes stableThe comparisons become n log n even on sorted input

5. How much extra memory does quick sort need when it recurses into the smaller part?O(n²)O(log n): only the stackO(n), as much as merge sort

Quick sort and the bad pivot

Cookies