Quick Sort

Category: Sorting

The problem

This repo's Merge Sort guarantees O(n log n) regardless of input order, but pays for that guarantee with an O(n) auxiliary buffer. What's needed for a large, memory-tight batch is average-case O(n log n) in place — no auxiliary array — accepting a worst case in exchange, as long as that worst case can be made vanishingly unlikely rather than something real, untrusted input could trigger on purpose or by accident.

The solution

Pick a pivot, partition the range so everything smaller than it ends up to its left and everything larger ends up to its right — entirely via swaps within the original array, no auxiliary buffer — then recurse on each side. The partition step is O(n); the average recursion depth is O(log n), giving average-case O(n log n). The catch: a fixed pivot choice (always the last element, say) hits its O(n²) worst case on exactly already-sorted or reverse-sorted input — precisely the two orderings this repo's benchmarks already test for every other sort. This implementation picks the pivot uniformly at random from the current range before every partition. That doesn't remove the worst case — it's still mathematically possible — but it ties the worst case to the random seed instead of the input's own order, which is what makes quicksort safe to run on input you don't control, rather than a landmine waiting for the one input shape that breaks it.

flowchart LR
    subgraph "partition around a pivot (7)"
        direction LR
        A0["5"] --- A1["3"] --- A2["9"] --- A3["1"] --- A4["7*"] --- A5["8"]
    end
    subgraph "after: smaller left, larger right, pivot fixed"
        direction LR
        B0["5"] --- B1["3"] --- B2["1"] --- B3["7*"] --- B4["9"] --- B5["8"]
    end

Classic example

classic/QuickSort is generic over Comparator<? super T> — no Arrays.sort/Collections.sort shortcut — using Lomuto partitioning with a randomized pivot swapped into the last position before every partition call. The public sort(array, comparator) uses an unseeded java.util.Random; a package-private sort(array, comparator, random) overload accepts an injected Random so tests can be deterministic. QuickSortTest covers an unordered array, already-sorted, reverse-sorted, duplicates, a single-element and an empty array, a custom (descending) comparator, the public unseeded overload, and both null-argument guards.

Applied example: insurance claim reserve percentile sort

applied/ClaimAmountSort sorts a large batch of insurance claims by amount for percentile-based reserve calculation (e.g. "what claim amount marks the 95th percentile this quarter"). Claim exports are commonly already close to sorted — by claim ID, which tends to correlate with filing date, which itself correlates loosely with amount for many claim types — which is exactly the kind of near-sorted input that would make a non-randomized quicksort degrade toward its worst case. Randomizing the pivot is what keeps this safe to run on a real, not synthetically-random, batch. ClaimAmountSortTest covers claims sorted into ascending amount order, that the input array is left untouched, and the null-argument guard.

Benchmark

./gradlew :sorting:quick-sort:jmh

Real run on this machine (JMH 1.37, JDK 26.0.2, 2 warmup + 3 measurement iterations, 1 fork). Already-sorted and reverse-sorted — the two orderings that would be catastrophic for a fixed-pivot quicksort — against fully random input:

That's the whole point, made measurable: at size=10,000, random is only ~2.2x more expensive than already-sorted — not the 100x-plus a non-randomized quicksort's O(n²) worst case would show on exactly this input. The randomized pivot is doing its job. Growth across sizes also confirms O(n log n), not O(n²): random goes from size=1,000 to size=10,000 (10x the data) at ~15.3x the cost — close to the ~13.3x an O(n log n) shape predicts, nowhere near the ~100x a quadratic sort would show for the same jump. Worth comparing against this repo's Merge Sort benchmark on the same machine: both land in a similar range at size=10,000 (quicksort ~1,000–2,200 µs here vs. merge sort's ~950–1,700 µs) — genuinely comparable average-case performance, with quicksort paying no auxiliary-buffer allocation and merge sort paying no worst-case risk.

When not to use it

• Need a guaranteed worst-case bound, not just an overwhelmingly likely one — a hard real-time system, or input you have to assume is adversarial? Merge Sort from this repo gives up the in-place property in exchange for a bound that doesn't depend on random luck.
• Need stability (equal elements keeping their original order)? This partitioning scheme doesn't preserve it — Merge Sort does.
• Very small n? Insertion Sort's lower constant factor wins before recursion overhead pays for itself — which is exactly why production quicksort implementations fall back to insertion sort below a small size threshold, the same fact this repo's own Insertion Sort module leans on.

Test coverage

100% instruction coverage, 100% branch coverage (JaCoCo). Reproduce it yourself:

./gradlew :sorting:quick-sort:jacocoTestReport

Report at sorting/quick-sort/build/reports/jacoco/test/html/index.html.

Further reading

• Cormen, Leiserson, Rivest & Stein — Introduction to Algorithms (CLRS), 3rd/4th ed., Chapter 7, "Quicksort", including section 7.3, "A randomized version of quicksort" — the formal treatment of exactly the randomization strategy this module implements.
• Sedgewick & Wayne — Algorithms, 4th ed., Chapter 2.3, "Quicksort" — includes the practical engineering refinements (random shuffle before sorting, cutoff to insertion sort for small subarrays) production implementations layer on top of the core algorithm.

Unit tests

package com.algorithms.sorting.quicksort.classic;

import org.junit.jupiter.api.Test;

import java.util.Comparator;
import java.util.Random;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class QuickSortTest {

    private static final Random SEEDED = new Random(42);

    @Test
    void sortsAnUnorderedArrayIntoAscendingOrder() {
        Integer[] array = {5, 3, 8, 1, 9, 2};

        QuickSort.sort(array, Comparator.naturalOrder(), SEEDED);

        assertThat(array).containsExactly(1, 2, 3, 5, 8, 9);
    }

    @Test
    void alreadySortedArrayStaysSorted() {
        Integer[] array = {1, 2, 3, 4, 5};

        QuickSort.sort(array, Comparator.naturalOrder(), SEEDED);

        assertThat(array).containsExactly(1, 2, 3, 4, 5);
    }

    @Test
    void reverseSortedArrayEndsUpAscending() {
        Integer[] array = {5, 4, 3, 2, 1};

        QuickSort.sort(array, Comparator.naturalOrder(), SEEDED);

        assertThat(array).containsExactly(1, 2, 3, 4, 5);
    }

    @Test
    void duplicatesAreHandledCorrectly() {
        Integer[] array = {3, 1, 3, 2, 1};

        QuickSort.sort(array, Comparator.naturalOrder(), SEEDED);

        assertThat(array).containsExactly(1, 1, 2, 3, 3);
    }

    @Test
    void singleElementArrayStaysUnchanged() {
        Integer[] array = {42};

        QuickSort.sort(array, Comparator.naturalOrder(), SEEDED);

        assertThat(array).containsExactly(42);
    }

    @Test
    void emptyArrayStaysEmpty() {
        Integer[] array = {};

        QuickSort.sort(array, Comparator.naturalOrder(), SEEDED);

        assertThat(array).isEmpty();
    }

    @Test
    void sortsUsingACustomComparatorForDescendingOrder() {
        Integer[] array = {1, 5, 3, 2, 4};

        QuickSort.sort(array, Comparator.reverseOrder(), SEEDED);

        assertThat(array).containsExactly(5, 4, 3, 2, 1);
    }

    @Test
    void publicSortMethodWorksWithoutAnExplicitRandom() {
        Integer[] array = {4, 2, 7, 1};

        QuickSort.sort(array, Comparator.naturalOrder());

        assertThat(array).containsExactly(1, 2, 4, 7);
    }

    @Test
    void rejectsANullArray() {
        assertThatThrownBy(() -> QuickSort.sort(null, Comparator.naturalOrder()))
                .isInstanceOf(IllegalArgumentException.class);
    }

    @Test
    void rejectsANullComparator() {
        assertThatThrownBy(() -> QuickSort.sort(new Integer[] {1, 2}, null))
                .isInstanceOf(IllegalArgumentException.class);
    }
}

package com.algorithms.sorting.quicksort.applied;

import org.junit.jupiter.api.Test;

import java.math.BigDecimal;

import static org.assertj.core.api.Assertions.assertThat;
import static org.assertj.core.api.Assertions.assertThatThrownBy;

class ClaimAmountSortTest {

    @Test
    void sortByAmountOrdersClaimsAscending() {
        ClaimAmountSort sorter = new ClaimAmountSort();
        InsuranceClaim[] claims = {
                claim("mid", "500.00"),
                claim("high", "9000.00"),
                claim("low", "12.50"),
        };

        InsuranceClaim[] sorted = sorter.sortByAmount(claims);

        assertThat(sorted).extracting(InsuranceClaim::claimId).containsExactly("low", "mid", "high");
    }

    @Test
    void doesNotMutateTheInputArray() {
        ClaimAmountSort sorter = new ClaimAmountSort();
        InsuranceClaim[] claims = {claim("b", "200.00"), claim("a", "10.00")};

        sorter.sortByAmount(claims);

        assertThat(claims).extracting(InsuranceClaim::claimId).containsExactly("b", "a");
    }

    @Test
    void rejectsNullClaims() {
        ClaimAmountSort sorter = new ClaimAmountSort();

        assertThatThrownBy(() -> sorter.sortByAmount(null)).isInstanceOf(IllegalArgumentException.class);
    }

    private static InsuranceClaim claim(String id, String amount) {
        return new InsuranceClaim(id, new BigDecimal(amount));
    }
}

View full JaCoCo coverage report →