Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Quick Sort and Partitioning

Editorial

The quick sort everyone writes

Quick sort picks a value, the pivot, moves everything smaller to its left and everything else to its right, and sorts the two sides the same way. The pivot is chosen at random, so no order of the input can make it slow on purpose. Here it is the way most people write it, on 50,000 random values and on 50,000 copies of one value, an array Sort an Array allows:

#include <bits/stdc++.h>
using namespace std;

uint32_t seed = 2463534242u;

int randomBelow(int bound) {                 // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed % bound;
}

vector<int> shuffled(int n) {                // 0 .. n-1 in a random order
    vector<int> nums(n);
    iota(nums.begin(), nums.end(), 0);
    for (int i = n - 1; i > 0; i--) swap(nums[i], nums[randomBelow(i + 1)]);
    return nums;
}

void quickSort(vector<int>& a, int lo, int hi) {   // Lomuto: a random pivot, one boundary, one scan
    if (lo >= hi) return;
    swap(a[lo + randomBelow(hi - lo + 1)], a[hi]);  // the pivot goes to the end
    int pivot = a[hi], b = lo;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) swap(a[b++], a[j]);       // smaller values go left of the boundary
    swap(a[b], a[hi]);                              // the pivot lands in its final place
    quickSort(a, lo, b - 1);
    quickSort(a, b + 1, hi);
}

int main() {
    int n = 50000;
    vector<int> random(n), equal(n, 7);
    for (int& v : random) v = randomBelow(100001) - 50000;
    for (auto& input : vector<pair<string, vector<int>*>>{{"random", &random}, {"equal", &equal}}) {
        const string& name = input.first;
        vector<int>* a = input.second;
        auto start = chrono::steady_clock::now();
        quickSort(*a, 0, n - 1);
        printf("%s: %.1f ms\n", name.c_str(), chrono::duration<double, milli>(chrono::steady_clock::now() - start).count());
    }
}

// random: 3.8 ms
// equal: 1224.0 ms
seed = 2463534242


def random_below(bound):              # xorshift: the same numbers in every language
    global seed
    seed ^= (seed << 13) & 0xFFFFFFFF
    seed ^= seed >> 17
    seed ^= (seed << 5) & 0xFFFFFFFF
    return seed % bound


def shuffled(n):                      # 0 .. n-1 in a random order
    nums = list(range(n))
    for i in range(n - 1, 0, -1):
        j = random_below(i + 1)
        nums[i], nums[j] = nums[j], nums[i]
    return nums

import time


def quick_sort(a, lo, hi):            # Lomuto: a random pivot, one boundary, one scan
    if lo >= hi:
        return
    r = lo + random_below(hi - lo + 1)
    a[r], a[hi] = a[hi], a[r]         # the pivot goes to the end
    pivot, b = a[hi], lo
    for j in range(lo, hi):
        if a[j] < pivot:              # smaller values go left of the boundary
            a[b], a[j] = a[j], a[b]
            b += 1
    a[b], a[hi] = a[hi], a[b]         # the pivot lands in its final place
    quick_sort(a, lo, b - 1)
    quick_sort(a, b + 1, hi)


n = 50000
inputs = {"random": [random_below(100001) - 50000 for _ in range(n)], "equal": [7] * n}
for name, a in inputs.items():
    start = time.perf_counter()
    try:
        quick_sort(a, 0, n - 1)
        print(f"{name}: {(time.perf_counter() - start) * 1000:.1f} ms")
    except RecursionError:
        print(f"{name}: RecursionError")

# random: 167.8 ms
# equal: RecursionError
public class Main {
    static int seed = (int) 2463534242L;

    static int randomBelow(int bound) {          // xorshift: the same numbers in every language
        seed ^= seed << 13;
        seed ^= seed >>> 17;
        seed ^= seed << 5;
        return Integer.remainderUnsigned(seed, bound);
    }

    static int[] shuffled(int n) {               // 0 .. n-1 in a random order
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = i;
        for (int i = n - 1; i > 0; i--) {
            int j = randomBelow(i + 1), t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        return nums;
    }

    static void quickSort(int[] a, int lo, int hi) {   // Lomuto: a random pivot, one boundary, one scan
        if (lo >= hi) return;
        int r = lo + randomBelow(hi - lo + 1), t = a[r];
        a[r] = a[hi]; a[hi] = t;                    // the pivot goes to the end
        int pivot = a[hi], b = lo;
        for (int j = lo; j < hi; j++)
            if (a[j] < pivot) { t = a[b]; a[b] = a[j]; a[j] = t; b++; }   // smaller values go left
        t = a[b]; a[b] = a[hi]; a[hi] = t;          // the pivot lands in its final place
        quickSort(a, lo, b - 1);
        quickSort(a, b + 1, hi);
    }

    public static void main(String[] args) {
        int n = 50000;
        int[] random = new int[n], equal = new int[n];
        for (int i = 0; i < n; i++) { random[i] = randomBelow(100001) - 50000; equal[i] = 7; }
        String[] names = {"random", "equal"};
        int[][] inputs = {random, equal};
        for (int k = 0; k < 2; k++) {
            long start = System.nanoTime();
            try {
                quickSort(inputs[k], 0, n - 1);
                System.out.printf("%s: %.1f ms%n", names[k], (System.nanoTime() - start) / 1e6);
            } catch (StackOverflowError e) {
                System.out.println(names[k] + ": StackOverflowError");
            }
        }
    }
}

// random: 14.4 ms
// equal: StackOverflowError
let seed = 2463534242;

function randomBelow(bound) {                // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >>> 17;
    seed ^= seed << 5;
    return (seed >>> 0) % bound;
}

function shuffled(n) {                       // 0 .. n-1 in a random order
    const nums = Array.from({ length: n }, (_, i) => i);
    for (let i = n - 1; i > 0; i--) {
        const j = randomBelow(i + 1);
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    return nums;
}

function quickSort(a, lo, hi) {           // Lomuto: a random pivot, one boundary, one scan
    if (lo >= hi) return;
    const r = lo + randomBelow(hi - lo + 1);
    [a[r], a[hi]] = [a[hi], a[r]];            // the pivot goes to the end
    const pivot = a[hi];
    let b = lo;
    for (let j = lo; j < hi; j++)
        if (a[j] < pivot) { [a[b], a[j]] = [a[j], a[b]]; b++; }   // smaller values go left
    [a[b], a[hi]] = [a[hi], a[b]];            // the pivot lands in its final place
    quickSort(a, lo, b - 1);
    quickSort(a, b + 1, hi);
}

const n = 50000;
const inputs = [["random", Array.from({ length: n }, () => randomBelow(100001) - 50000)], ["equal", new Array(n).fill(7)]];
for (const [name, a] of inputs) {
    const start = process.hrtime.bigint();
    try {
        quickSort(a, 0, n - 1);
        console.log(`${name}: ${(Number(process.hrtime.bigint() - start) / 1e6).toFixed(1)} ms`);
    } catch (e) {
        if (!(e instanceof RangeError)) throw e;
        console.log(`${name}: RangeError`);
    }
}

// random: 43.7 ms
// equal: RangeError

The random values took 3.8 ms in C++. The equal ones took 1.22 s, 322 times longer, and the other three never finished: Java threw StackOverflowError, JavaScript RangeError and Python RecursionError.

When every value equals the pivot, none is smaller, so the pivot lands at one end and the other side keeps everything but one value: n − 1, then n − 2, and so on. That's n²/2 comparisons and a call stack 50,000 deep. A random pivot protects against sorted input (Best, Worst and Average Case timed that trap); it can't help when every pivot is the same. This lesson takes partitioning apart, then fixes it twice.

Two dashed panels. Left, partition around the last value: before, the tiles 7 2 1 8 6 3 5 4, with 2, 1 and 3 in blue and the pivot 4 in orange, ringed; an arrow down marked one scan; after, 2 1 3 in blue labelled smaller, 4 in orange ringed in green labelled its place, and 6 7 5 8 in purple labelled not smaller, with the pills sort 2 1 3 and sort 6 7 5 8. Right, the scan, pivot 4: 2 < 4: swap with 7, the boundary moves to 1; 1 < 4: swap with 7, the boundary moves to 2; 3 < 4: swap with 7, the boundary moves to 3; 7, 8, 6, 5 aren't smaller: they stay right of the boundary; end: 4 swaps with 8, index 3, never to move again. Focal line: one scan puts the pivot in its final place. Title: one pass puts the pivot in place.

Partitioning: one scan, one boundary

The partition above is Lomuto's. The pivot waits at the end; a boundary b starts at the left; one index j scans the rest. Each value smaller than the pivot is swapped to the boundary, which moves one place right. At the end the pivot is swapped to the boundary, and everything before it is smaller, everything after it is not:

#include <bits/stdc++.h>
using namespace std;

int partition(vector<int>& a, int lo, int hi) {   // Lomuto around the last value; returns where it lands
    int pivot = a[hi], b = lo;
    for (int j = lo; j < hi; j++)
        if (a[j] < pivot) swap(a[b++], a[j]);
    swap(a[b], a[hi]);
    return b;
}

int main() {
    vector<int> a = {7, 2, 1, 8, 6, 3, 5, 4};
    int p = partition(a, 0, a.size() - 1);
    for (int v : a) printf("%d ", v);
    printf("| the pivot %d is at %d\n", a[p], p);
}

// 2 1 3 4 6 7 5 8 | the pivot 4 is at 3
def partition(a, lo, hi):             # Lomuto around the last value; returns where it lands
    pivot, b = a[hi], lo
    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]
    return b


a = [7, 2, 1, 8, 6, 3, 5, 4]
p = partition(a, 0, len(a) - 1)
print(*a, f"| the pivot {a[p]} is at {p}")

# 2 1 3 4 6 7 5 8 | the pivot 4 is at 3
public class Main {
    static int partition(int[] a, int lo, int hi) {   // Lomuto around the last value; returns where it lands
        int pivot = a[hi], b = lo, t;
        for (int j = lo; j < hi; j++)
            if (a[j] < pivot) { t = a[b]; a[b] = a[j]; a[j] = t; b++; }
        t = a[b]; a[b] = a[hi]; a[hi] = t;
        return b;
    }

    public static void main(String[] args) {
        int[] a = {7, 2, 1, 8, 6, 3, 5, 4};
        int p = partition(a, 0, a.length - 1);
        StringBuilder line = new StringBuilder();
        for (int v : a) line.append(v).append(" ");
        System.out.println(line + "| the pivot " + a[p] + " is at " + p);
    }
}

// 2 1 3 4 6 7 5 8 | the pivot 4 is at 3
function partition(a, lo, hi) {           // Lomuto around the last value; returns where it lands
    const pivot = a[hi];
    let b = lo;
    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]];
    return b;
}

const a = [7, 2, 1, 8, 6, 3, 5, 4];
const p = partition(a, 0, a.length - 1);
console.log(`${a.join(" ")} | the pivot ${a[p]} is at ${p}`);

// 2 1 3 4 6 7 5 8 | the pivot 4 is at 3

4 landed at index 3, its place in sorted order, and never moves again. Then quick sort recurses on 2 1 3 and on 6 7 5 8. Each partition is O(n), and when the pivot splits the values roughly in half, there are about log₂ n levels: O(n log n) on average, in place, with O(log n) of call stack. When the pivot lands at an end every time, it's O(n²), as above. Quick sort isn't stable: the swaps jump values over their equals.

Partition and Quickselect. Run Lomuto's partition yourself: for each value, decide whether it's smaller than the pivot and swaps to the boundary. Then say which side holds the kth smallest, the step quickselect repeats. Try the equal values to watch the pivot land at the end.

Partition and Quickselect: run Lomuto's partition, then pick the side

Hoare's partition: two indexes

Hoare's partition, the original, moves two indexes toward each other: i stops at a value that belongs on the right (not smaller than the pivot), j stops at one that belongs on the left (not bigger), and the two swap. Values equal to the pivot stop both indexes, so equal values are swapped and spread across both sides:

#include <bits/stdc++.h>
using namespace std;

uint32_t seed = 2463534242u;

int randomBelow(int bound) {                 // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed % bound;
}

vector<int> shuffled(int n) {                // 0 .. n-1 in a random order
    vector<int> nums(n);
    iota(nums.begin(), nums.end(), 0);
    for (int i = n - 1; i > 0; i--) swap(nums[i], nums[randomBelow(i + 1)]);
    return nums;
}

void quickSort(vector<int>& a, int lo, int hi) {   // Hoare: two indexes close in from both ends
    if (lo >= hi) return;
    swap(a[lo], a[lo + randomBelow(hi - lo + 1)]); // a random pivot, moved to the front
    int pivot = a[lo], i = lo - 1, j = hi + 1;
    while (true) {
        do i++; while (a[i] < pivot);              // stop at a value that belongs on the right...
        do j--; while (a[j] > pivot);              // ...and at one that belongs on the left
        if (i >= j) break;
        swap(a[i], a[j]);
    }
    quickSort(a, lo, j);                            // a[lo..j] <= pivot <= a[j+1..hi]
    quickSort(a, j + 1, hi);
}

int main() {
    int n = 50000;
    vector<int> random(n), equal(n, 7);
    for (int& v : random) v = randomBelow(100001) - 50000;
    for (auto& input : vector<pair<string, vector<int>*>>{{"random", &random}, {"equal", &equal}}) {
        const string& name = input.first;
        vector<int>* a = input.second;
        auto start = chrono::steady_clock::now();
        quickSort(*a, 0, n - 1);
        if (!is_sorted(a->begin(), a->end())) return 1;
        printf("%s: %.1f ms\n", name.c_str(), chrono::duration<double, milli>(chrono::steady_clock::now() - start).count());
    }
}

// random: 4.5 ms
// equal: 1.0 ms
seed = 2463534242


def random_below(bound):              # xorshift: the same numbers in every language
    global seed
    seed ^= (seed << 13) & 0xFFFFFFFF
    seed ^= seed >> 17
    seed ^= (seed << 5) & 0xFFFFFFFF
    return seed % bound


def shuffled(n):                      # 0 .. n-1 in a random order
    nums = list(range(n))
    for i in range(n - 1, 0, -1):
        j = random_below(i + 1)
        nums[i], nums[j] = nums[j], nums[i]
    return nums

import time


def quick_sort(a, lo, hi):            # Hoare: two indexes close in from both ends
    if lo >= hi:
        return
    r = lo + random_below(hi - lo + 1)
    a[lo], a[r] = a[r], a[lo]         # a random pivot, moved to the front
    pivot, i, j = a[lo], lo - 1, hi + 1
    while True:
        i += 1
        while a[i] < pivot:           # stop at a value that belongs on the right...
            i += 1
        j -= 1
        while a[j] > pivot:           # ...and at one that belongs on the left
            j -= 1
        if i >= j:
            break
        a[i], a[j] = a[j], a[i]
    quick_sort(a, lo, j)              # a[lo..j] <= pivot <= a[j+1..hi]
    quick_sort(a, j + 1, hi)


n = 50000
inputs = {"random": [random_below(100001) - 50000 for _ in range(n)], "equal": [7] * n}
for name, a in inputs.items():
    start = time.perf_counter()
    quick_sort(a, 0, n - 1)
    assert a == sorted(a)
    print(f"{name}: {(time.perf_counter() - start) * 1000:.1f} ms")

# random: 180.7 ms
# equal: 175.5 ms
public class Main {
    static int seed = (int) 2463534242L;

    static int randomBelow(int bound) {          // xorshift: the same numbers in every language
        seed ^= seed << 13;
        seed ^= seed >>> 17;
        seed ^= seed << 5;
        return Integer.remainderUnsigned(seed, bound);
    }

    static int[] shuffled(int n) {               // 0 .. n-1 in a random order
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = i;
        for (int i = n - 1; i > 0; i--) {
            int j = randomBelow(i + 1), t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        return nums;
    }

    static void quickSort(int[] a, int lo, int hi) {   // Hoare: two indexes close in from both ends
        if (lo >= hi) return;
        int r = lo + randomBelow(hi - lo + 1), t = a[lo];
        a[lo] = a[r]; a[r] = t;                     // a random pivot, moved to the front
        int pivot = a[lo], i = lo - 1, j = hi + 1;
        while (true) {
            do i++; while (a[i] < pivot);           // stop at a value that belongs on the right...
            do j--; while (a[j] > pivot);           // ...and at one that belongs on the left
            if (i >= j) break;
            t = a[i]; a[i] = a[j]; a[j] = t;
        }
        quickSort(a, lo, j);                        // a[lo..j] <= pivot <= a[j+1..hi]
        quickSort(a, j + 1, hi);
    }

    public static void main(String[] args) {
        int n = 50000;
        int[] random = new int[n], equal = new int[n];
        for (int i = 0; i < n; i++) { random[i] = randomBelow(100001) - 50000; equal[i] = 7; }
        String[] names = {"random", "equal"};
        int[][] inputs = {random, equal};
        for (int k = 0; k < 2; k++) {
            long start = System.nanoTime();
            quickSort(inputs[k], 0, n - 1);
            for (int i = 1; i < n; i++) if (inputs[k][i - 1] > inputs[k][i]) throw new AssertionError();
            System.out.printf("%s: %.1f ms%n", names[k], (System.nanoTime() - start) / 1e6);
        }
    }
}

// random: 37.6 ms
// equal: 6.5 ms
let seed = 2463534242;

function randomBelow(bound) {                // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >>> 17;
    seed ^= seed << 5;
    return (seed >>> 0) % bound;
}

function shuffled(n) {                       // 0 .. n-1 in a random order
    const nums = Array.from({ length: n }, (_, i) => i);
    for (let i = n - 1; i > 0; i--) {
        const j = randomBelow(i + 1);
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    return nums;
}

function quickSort(a, lo, hi) {           // Hoare: two indexes close in from both ends
    if (lo >= hi) return;
    const r = lo + randomBelow(hi - lo + 1);
    [a[lo], a[r]] = [a[r], a[lo]];            // a random pivot, moved to the front
    const pivot = a[lo];
    let i = lo - 1, j = hi + 1;
    while (true) {
        do i++; while (a[i] < pivot);         // stop at a value that belongs on the right...
        do j--; while (a[j] > pivot);         // ...and at one that belongs on the left
        if (i >= j) break;
        [a[i], a[j]] = [a[j], a[i]];
    }
    quickSort(a, lo, j);                      // a[lo..j] <= pivot <= a[j+1..hi]
    quickSort(a, j + 1, hi);
}

const n = 50000;
const inputs = [["random", Array.from({ length: n }, () => randomBelow(100001) - 50000)], ["equal", new Array(n).fill(7)]];
for (const [name, a] of inputs) {
    const start = process.hrtime.bigint();
    quickSort(a, 0, n - 1);
    if (a.some((v, i) => i > 0 && a[i - 1] > v)) throw new Error("not sorted");
    console.log(`${name}: ${(Number(process.hrtime.bigint() - start) / 1e6).toFixed(1)} ms`);
}

// random: 33.6 ms
// equal: 17.6 ms

The 50,000 equal values took 1.0 ms in C++, 6.5 ms in Java, 18 ms in JavaScript and 176 ms in Python: i and j meet in the middle, every split is even, and the recursion is log₂ n deep. Its catch is the boundary: the pivot isn't put in its final place, so it recurses on [lo, j] and [j + 1, hi], and the pivot must not be the last value (Mistakes that cost an interview).

Three-way partition: the equal values in the middle

The three-way partition (Dijkstra's Dutch national flag) splits into smaller, equal and bigger. Three indexes: below lt everything is smaller, from lt to i equal, above gt bigger, and i walks until it meets gt. The equal block is finished, and only the two outer parts recurse. Sort Colors, in Two Pointers, is exactly this partition on three values:

Three dashed panels, each with eight tiles of 5 above the same eight after one partition. Lomuto, crossed: the first 5 orange and ringed, the other seven purple; 0 | 7; nothing is smaller, so the pivot lands in front: 7 recurse; O(n²), n calls deep. Hoare, ticked: four blue, four purple; 4 | 4; i and j stop at every 5, swap, and meet in the middle; O(n log n). Three-way, ticked: all eight green; done; every value is the pivot: all go in the equal block; O(n), one pass. Focal line: equal values: split them evenly, or finish them in one pass. Title: equal values and three partitions.
#include <bits/stdc++.h>
using namespace std;

uint32_t seed = 2463534242u;

int randomBelow(int bound) {                 // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed % bound;
}

vector<int> shuffled(int n) {                // 0 .. n-1 in a random order
    vector<int> nums(n);
    iota(nums.begin(), nums.end(), 0);
    for (int i = n - 1; i > 0; i--) swap(nums[i], nums[randomBelow(i + 1)]);
    return nums;
}

void quickSort(vector<int>& a, int lo, int hi) {   // three ways: < pivot | = pivot | > pivot
    if (lo >= hi) return;
    int pivot = a[lo + randomBelow(hi - lo + 1)], lt = lo, i = lo, gt = hi;
    while (i <= gt) {
        if (a[i] < pivot) swap(a[lt++], a[i++]);
        else if (a[i] > pivot) swap(a[i], a[gt--]);  // a[i] is new: look at it next
        else i++;
    }
    quickSort(a, lo, lt - 1);                       // the equal values in a[lt..gt] are done
    quickSort(a, gt + 1, hi);
}

int main() {
    int n = 50000;
    vector<int> random(n), equal(n, 7), few(n);
    for (int& v : random) v = randomBelow(100001) - 50000;
    for (int& v : few) v = randomBelow(3);
    for (auto& input : vector<pair<string, vector<int>*>>{{"random", &random}, {"equal", &equal}, {"0 to 2", &few}}) {
        const string& name = input.first;
        vector<int>* a = input.second;
        auto start = chrono::steady_clock::now();
        quickSort(*a, 0, n - 1);
        if (!is_sorted(a->begin(), a->end())) return 1;
        printf("%s: %.1f ms\n", name.c_str(), chrono::duration<double, milli>(chrono::steady_clock::now() - start).count());
    }
}

// random: 4.5 ms
// equal: 0.1 ms
// 0 to 2: 0.5 ms
seed = 2463534242


def random_below(bound):              # xorshift: the same numbers in every language
    global seed
    seed ^= (seed << 13) & 0xFFFFFFFF
    seed ^= seed >> 17
    seed ^= (seed << 5) & 0xFFFFFFFF
    return seed % bound


def shuffled(n):                      # 0 .. n-1 in a random order
    nums = list(range(n))
    for i in range(n - 1, 0, -1):
        j = random_below(i + 1)
        nums[i], nums[j] = nums[j], nums[i]
    return nums

import time


def quick_sort(a, lo, hi):            # three ways: < pivot | = pivot | > pivot
    if lo >= hi:
        return
    pivot = a[lo + random_below(hi - lo + 1)]
    lt, i, gt = lo, lo, hi
    while i <= gt:
        if a[i] < pivot:
            a[lt], a[i] = a[i], a[lt]
            lt += 1
            i += 1
        elif a[i] > pivot:
            a[i], a[gt] = a[gt], a[i]
            gt -= 1                   # a[i] is new: look at it next
        else:
            i += 1
    quick_sort(a, lo, lt - 1)         # the equal values in a[lt..gt] are done
    quick_sort(a, gt + 1, hi)


n = 50000
inputs = {"random": [random_below(100001) - 50000 for _ in range(n)], "equal": [7] * n,
          "0 to 2": [random_below(3) for _ in range(n)]}
for name, a in inputs.items():
    start = time.perf_counter()
    quick_sort(a, 0, n - 1)
    assert a == sorted(a)
    print(f"{name}: {(time.perf_counter() - start) * 1000:.1f} ms")

# random: 256.9 ms
# equal: 6.9 ms
# 0 to 2: 18.4 ms
public class Main {
    static int seed = (int) 2463534242L;

    static int randomBelow(int bound) {          // xorshift: the same numbers in every language
        seed ^= seed << 13;
        seed ^= seed >>> 17;
        seed ^= seed << 5;
        return Integer.remainderUnsigned(seed, bound);
    }

    static int[] shuffled(int n) {               // 0 .. n-1 in a random order
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = i;
        for (int i = n - 1; i > 0; i--) {
            int j = randomBelow(i + 1), t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        return nums;
    }

    static void quickSort(int[] a, int lo, int hi) {   // three ways: < pivot | = pivot | > pivot
        if (lo >= hi) return;
        int pivot = a[lo + randomBelow(hi - lo + 1)], lt = lo, i = lo, gt = hi, t;
        while (i <= gt) {
            if (a[i] < pivot) { t = a[lt]; a[lt++] = a[i]; a[i++] = t; }
            else if (a[i] > pivot) { t = a[i]; a[i] = a[gt]; a[gt--] = t; }   // a[i] is new: look at it next
            else i++;
        }
        quickSort(a, lo, lt - 1);                   // the equal values in a[lt..gt] are done
        quickSort(a, gt + 1, hi);
    }

    public static void main(String[] args) {
        int n = 50000;
        int[] random = new int[n], equal = new int[n], few = new int[n];
        for (int i = 0; i < n; i++) { random[i] = randomBelow(100001) - 50000; equal[i] = 7; }
        for (int i = 0; i < n; i++) few[i] = randomBelow(3);
        String[] names = {"random", "equal", "0 to 2"};
        int[][] inputs = {random, equal, few};
        for (int k = 0; k < 3; k++) {
            long start = System.nanoTime();
            quickSort(inputs[k], 0, n - 1);
            for (int i = 1; i < n; i++) if (inputs[k][i - 1] > inputs[k][i]) throw new AssertionError();
            System.out.printf("%s: %.1f ms%n", names[k], (System.nanoTime() - start) / 1e6);
        }
    }
}

// random: 17.4 ms
// equal: 0.7 ms
// 0 to 2: 1.4 ms
let seed = 2463534242;

function randomBelow(bound) {                // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >>> 17;
    seed ^= seed << 5;
    return (seed >>> 0) % bound;
}

function shuffled(n) {                       // 0 .. n-1 in a random order
    const nums = Array.from({ length: n }, (_, i) => i);
    for (let i = n - 1; i > 0; i--) {
        const j = randomBelow(i + 1);
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    return nums;
}

function quickSort(a, lo, hi) {           // three ways: < pivot | = pivot | > pivot
    if (lo >= hi) return;
    const pivot = a[lo + randomBelow(hi - lo + 1)];
    let lt = lo, i = lo, gt = hi;
    while (i <= gt) {
        if (a[i] < pivot) { [a[lt], a[i]] = [a[i], a[lt]]; lt++; i++; }
        else if (a[i] > pivot) { [a[i], a[gt]] = [a[gt], a[i]]; gt--; }   // a[i] is new: look at it next
        else i++;
    }
    quickSort(a, lo, lt - 1);                 // the equal values in a[lt..gt] are done
    quickSort(a, gt + 1, hi);
}

const n = 50000;
const inputs = [["random", Array.from({ length: n }, () => randomBelow(100001) - 50000)], ["equal", new Array(n).fill(7)],
    ["0 to 2", Array.from({ length: n }, () => randomBelow(3))]];
for (const [name, a] of inputs) {
    const start = process.hrtime.bigint();
    quickSort(a, 0, n - 1);
    if (a.some((v, i) => i > 0 && a[i - 1] > v)) throw new Error("not sorted");
    console.log(`${name}: ${(Number(process.hrtime.bigint() - start) / 1e6).toFixed(1)} ms`);
}

// random: 53.4 ms
// equal: 15.5 ms
// 0 to 2: 2.8 ms

All equal is a single pass: every value is the pivot, and nothing is left to recurse on. Each partition finishes every copy of its pivot, so values from 0 to 2 take three partitions in all, one per distinct value. On 50,000 equal values:

LanguageLomutoHoareThree-way
C++1.22 s1.0 ms0.1 ms
PythonRecursionError176 ms6.9 ms
JavaStackOverflowError6.5 ms0.7 ms
JavaScriptRangeError18 ms16 ms

Two more defences finish the picture. Median of three takes the middle of the first, middle and last values as the pivot, which beats sorted input without a random number. Introsort, behind C++'s sort, counts how deep the recursion gets and switches to heap sort (Introduction to Heaps) past about 2 log₂ n levels, so its worst case is O(n log n).

Quickselect: keep one side

To find the kth smallest value, partition once and look where the pivot block landed: if k falls in it, the pivot is the answer; otherwise keep only the side that holds k and partition again. One side per step, so the work halves on average: n + n/2 + n/4 + … ≈ 2n, O(n), where sorting is O(n log n). Top K and the Kth Element uses it for Kth Largest Element in an Array:

#include <bits/stdc++.h>
using namespace std;

uint32_t seed = 2463534242u;

int randomBelow(int bound) {                 // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >> 17;
    seed ^= seed << 5;
    return seed % bound;
}

vector<int> shuffled(int n) {                // 0 .. n-1 in a random order
    vector<int> nums(n);
    iota(nums.begin(), nums.end(), 0);
    for (int i = n - 1; i > 0; i--) swap(nums[i], nums[randomBelow(i + 1)]);
    return nums;
}

int quickselect(vector<int> a, int k) {          // the kth smallest, k from 1: partition, keep one side
    int lo = 0, hi = a.size() - 1;
    while (true) {
        int pivot = a[lo + randomBelow(hi - lo + 1)], lt = lo, i = lo, gt = hi;
        while (i <= gt) {
            if (a[i] < pivot) swap(a[lt++], a[i++]);
            else if (a[i] > pivot) swap(a[i], a[gt--]);
            else i++;
        }
        if (k - 1 < lt) hi = lt - 1;             // it's among the smaller values
        else if (k - 1 > gt) lo = gt + 1;        // among the bigger ones
        else return pivot;                       // it's the pivot
    }
}

int main() {
    vector<int> a = {7, 2, 1, 8, 6, 3, 5, 4};
    printf("%d %d %d %d\n", quickselect(a, 1), quickselect(a, 3), quickselect(a, 8), quickselect(vector<int>(10, 5), 4));
}

// 1 3 8 5
seed = 2463534242


def random_below(bound):              # xorshift: the same numbers in every language
    global seed
    seed ^= (seed << 13) & 0xFFFFFFFF
    seed ^= seed >> 17
    seed ^= (seed << 5) & 0xFFFFFFFF
    return seed % bound


def shuffled(n):                      # 0 .. n-1 in a random order
    nums = list(range(n))
    for i in range(n - 1, 0, -1):
        j = random_below(i + 1)
        nums[i], nums[j] = nums[j], nums[i]
    return nums


def quickselect(a, k):                # the kth smallest, k from 1: partition, keep one side
    a = a[:]
    lo, hi = 0, len(a) - 1
    while True:
        pivot = a[lo + random_below(hi - lo + 1)]
        lt, i, gt = lo, lo, hi
        while i <= gt:
            if a[i] < pivot:
                a[lt], a[i] = a[i], a[lt]
                lt += 1
                i += 1
            elif a[i] > pivot:
                a[i], a[gt] = a[gt], a[i]
                gt -= 1
            else:
                i += 1
        if k - 1 < lt:                # it's among the smaller values
            hi = lt - 1
        elif k - 1 > gt:              # among the bigger ones
            lo = gt + 1
        else:                         # it's the pivot
            return pivot


a = [7, 2, 1, 8, 6, 3, 5, 4]
print(quickselect(a, 1), quickselect(a, 3), quickselect(a, 8), quickselect([5] * 10, 4))

# 1 3 8 5
import java.util.*;

public class Main {
    static int seed = (int) 2463534242L;

    static int randomBelow(int bound) {          // xorshift: the same numbers in every language
        seed ^= seed << 13;
        seed ^= seed >>> 17;
        seed ^= seed << 5;
        return Integer.remainderUnsigned(seed, bound);
    }

    static int[] shuffled(int n) {               // 0 .. n-1 in a random order
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = i;
        for (int i = n - 1; i > 0; i--) {
            int j = randomBelow(i + 1), t = nums[i];
            nums[i] = nums[j];
            nums[j] = t;
        }
        return nums;
    }

    static int quickselect(int[] values, int k) {   // the kth smallest, k from 1: partition, keep one side
        int[] a = values.clone();
        int lo = 0, hi = a.length - 1;
        while (true) {
            int pivot = a[lo + randomBelow(hi - lo + 1)], lt = lo, i = lo, gt = hi, t;
            while (i <= gt) {
                if (a[i] < pivot) { t = a[lt]; a[lt++] = a[i]; a[i++] = t; }
                else if (a[i] > pivot) { t = a[i]; a[i] = a[gt]; a[gt--] = t; }
                else i++;
            }
            if (k - 1 < lt) hi = lt - 1;            // it's among the smaller values
            else if (k - 1 > gt) lo = gt + 1;       // among the bigger ones
            else return pivot;                      // it's the pivot
        }
    }

    public static void main(String[] args) {
        int[] a = {7, 2, 1, 8, 6, 3, 5, 4}, fives = new int[10];
        Arrays.fill(fives, 5);
        System.out.println(quickselect(a, 1) + " " + quickselect(a, 3) + " " + quickselect(a, 8) + " " + quickselect(fives, 4));
    }
}

// 1 3 8 5
let seed = 2463534242;

function randomBelow(bound) {                // xorshift: the same numbers in every language
    seed ^= seed << 13;
    seed ^= seed >>> 17;
    seed ^= seed << 5;
    return (seed >>> 0) % bound;
}

function shuffled(n) {                       // 0 .. n-1 in a random order
    const nums = Array.from({ length: n }, (_, i) => i);
    for (let i = n - 1; i > 0; i--) {
        const j = randomBelow(i + 1);
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    return nums;
}

function quickselect(values, k) {         // the kth smallest, k from 1: partition, keep one side
    const a = values.slice();
    let lo = 0, hi = a.length - 1;
    while (true) {
        const pivot = a[lo + randomBelow(hi - lo + 1)];
        let lt = lo, i = lo, gt = hi;
        while (i <= gt) {
            if (a[i] < pivot) { [a[lt], a[i]] = [a[i], a[lt]]; lt++; i++; }
            else if (a[i] > pivot) { [a[i], a[gt]] = [a[gt], a[i]]; gt--; }
            else i++;
        }
        if (k - 1 < lt) hi = lt - 1;          // it's among the smaller values
        else if (k - 1 > gt) lo = gt + 1;     // among the bigger ones
        else return pivot;                    // it's the pivot
    }
}

const a = [7, 2, 1, 8, 6, 3, 5, 4];
console.log(quickselect(a, 1), quickselect(a, 3), quickselect(a, 8), quickselect(new Array(10).fill(5), 4));

// 1 3 8 5

The 1st, 3rd and 8th smallest of the eight values are 1, 3 and 8, and the 4th smallest of ten 5s is 5, found in a single pass by the three-way partition. Like quick sort, its worst case is O(n²), and the random pivot makes that unlikely.

Which sort for Sort an Array

Sort an Array asks for O(n log n) time with no library sort, on up to 50,000 values from −50,000 to 50,000, and nothing stops a test from being one value 50,000 times. Three answers pass:

  • Merge sort (Merge Sort and Counting Inversions): O(n log n) always, stable, O(n) extra.
  • Quick sort with a random pivot and a three-way partition: in place, O(log n) stack on average, and equal values cost one pass.
  • Heap sort (Introduction to Heaps): O(n log n) always, O(1) extra, not stable.

Lomuto with a random pivot is the one that fails, as the first run showed; with a values range this small, counting sort works too (Counting, Bucket and Radix Sort).

Spotting it

The clues: "kth smallest" or "kth largest", the median, "top k" without the order of the k (quickselect, O(n) on average); rearranging around a value (all negatives first, colours, a pivot); sorting in place with O(1) extra space. Near misses:

  • The k largest of a stream that keeps growing: a heap, since quickselect needs every value at once (Top K and the Kth Element).
  • A sort that must keep equal values in order: merge sort, not quick sort.
  • Three known values to arrange in one pass: the three-way partition alone (Sort Colors).

Mistakes that cost an interview

Lomuto on many equal values. The random pivot doesn't help: 1.22 s in C++ and a stack error in Java, JavaScript and Python above. Use Hoare or the three-way partition.

Hoare's partition with the last value as the pivot. On two values, j can stop at hi, and the recursion calls the same range again:

def quick_sort(a, lo, hi):            # Hoare's loop, but with the last value as the pivot
    if lo >= hi:
        return
    pivot, i, j = a[hi], lo - 1, hi + 1
    while True:
        i += 1
        while a[i] < pivot:
            i += 1
        j -= 1
        while a[j] > pivot:
            j -= 1
        if i >= j:
            break
        a[i], a[j] = a[j], a[i]
    quick_sort(a, lo, j)              # j can be hi here: the same range again
    quick_sort(a, j + 1, hi)


try:
    quick_sort([1, 2], 0, 1)
except RecursionError:
    print("RecursionError on [1, 2]")

# RecursionError on [1, 2]

Take the pivot from the front, or move a random one there, as above; then j always stops before hi.

A first or last pivot on sorted input. O(n²) and a deep stack (Best, Worst and Average Case measured it); pick the pivot at random, or by median of three.

Expecting it to be stable. It isn't; if equal keys must keep their order, merge sort is the sort to use.

Check yourself

Quiz

1 / 6

Multiple choice

Lomuto's partition of [7, 2, 1, 8, 6, 3, 5, 4] around the last value: where does the 4 land?

Practice

In this section:

  • Quick Sort: a partition, then both sides; pick the pivot well.
  • Sort an Array: O(n log n) on inputs full of repeats: three-way quick sort or merge sort.

Next: Counting, Bucket and Radix Sort, the sorts that don't compare at all.