Merge Sort

Category: Sorting

The problem

This repo's Bubble Sort and Insertion Sort are both adaptive — genuinely fast on nearly-sorted input — but that adaptivity is exactly what makes them a liability the moment input order can't be trusted: both degrade to O(n²) on the wrong input, unpredictably, with no guardrail. A large batch, or one whose order an adversary could influence, needs a bound that holds regardless of how the input arrives — not a best case that only pays off when you get lucky.

The solution

Split the array in half, recursively sort each half, then merge the two already-sorted halves back together. Splitting bottoms out at single elements (trivially sorted); merging two sorted sequences only ever needs to compare their current heads and take the smaller one, which is what makes the merge step itself linear. Because the split point is always the midpoint — not data-dependent, unlike this repo's Quick Sort — the recursion depth is always exactly log2(n), and every level does O(n) total merge work: O(n log n), unconditionally, no input order gets a vote. The one real cost: merging needs an auxiliary buffer, so this is O(n) extra space, not in-place. Taking from the left half whenever the comparator reports a tie is also what makes this sort stable — equal elements keep their original relative order.

flowchart TB
    subgraph "split"
        direction TB
        S0["[5,3,8,1]"] --> S1["[5,3]"] & S2["[8,1]"]
        S1 --> S3["[5]"] & S4["[3]"]
        S2 --> S5["[8]"] & S6["[1]"]
    end
    subgraph "merge back up"
        direction TB
        M4["[5]"] & M3["[3]"] --> M1["[3,5]"]
        M6["[1]"] & M5["[8]"] --> M2["[1,8]"]
        M1 --> M0["[1,3,5,8]"]
        M2 --> M0
    end

Classic example

classic/MergeSort is generic over Comparator<? super T> — no Arrays.sort/Collections.sort shortcut. A single Object[] buffer is allocated once up front and reused across the whole recursion (only the relevant sub-range gets copied into it per merge), instead of allocating a fresh array at every recursive call. MergeSortTest covers an unordered array, already-sorted, reverse-sorted, an odd-sized array (exercises the uneven split), a single-element and an empty array, a custom (descending) comparator, both null-argument guards, and — directly proving the stability claim — a tagged-element test that sorts on a value that has duplicates and asserts the duplicates keep their original relative order.

Applied example: fraud compliance report ordering

applied/ComplianceReportSort orders fraud-flagged transactions by risk score, highest first, for a compliance report that has to be reproducible run over run: the same input must always produce the exact same output ordering, including how transactions tied on risk score are broken. Merge sort's guaranteed O(n log n) worst case protects against a large, duplicate-score-heavy batch degrading unpredictably, and its stability means transactions with the same score keep the order they were originally flagged in — an auditor re-running this report later gets an identical result, not just an equally-valid one. ComplianceReportSortTest covers descending ordering by score, ties preserving original flagging order, that the input array is left untouched, and the null-argument guard.

Benchmark

./gradlew :sorting:merge-sort:jmh

Real run on this machine (JMH 1.37, JDK 26.0.2, 2 warmup + 3 measurement iterations, 1 fork). Same three orderings and sizes as this repo's Bubble Sort and Insertion Sort benchmarks — the point here is the contrast:

Already-sorted and nearly-sorted track each other almost exactly at every size — input order genuinely doesn't matter here, unlike the 1,000x-plus gaps Bubble Sort and Insertion Sort show between their best and worst cases on this same machine. Random is consistently the most expensive of the three, but only by roughly 1.8–2x, not orders of magnitude — real work, not a degenerate case. And the growth shape across sizes confirms O(n log n), not O(n²): going from size=1,000 to size=10,000 (10x the data), the random case costs ~11.7x more — close to the ~13.3x an O(n log n) shape predicts for that jump (10,000·log₂(10,000) ÷ 1,000·log₂(1,000)), nowhere near the ~100x a quadratic sort would show for the same size increase.

When not to use it

• Tight memory budget, or need a genuinely in-place sort? Merge sort's O(n) auxiliary buffer is the one real cost of its guaranteed bound — Quick Sort or Heap Sort from this repo sort in place instead.
• Input is small and already close to sorted? Insertion Sort's lower constant factor wins at that scale — this module's own benchmark shows merge sort paying roughly the same cost whether the input is sorted or not, which is the point, but it's not free.
• Don't actually need the stability guarantee and want the best average-case constant factor in practice? Quick Sort usually edges out merge sort in wall-clock time on typical (non-adversarial) input, at the cost of losing the worst-case guarantee this module provides.

Test coverage

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

./gradlew :sorting:merge-sort:jacocoTestReport

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

Further reading

• Cormen, Leiserson, Rivest & Stein — Introduction to Algorithms (CLRS), 3rd/4th ed., Chapter 2.3, "Designing algorithms" — merge sort is CLRS's canonical divide-and-conquer example, with the recurrence T(n) = 2T(n/2) + O(n) this module's benchmark measures the real-world shape of.
• Sedgewick & Wayne — Algorithms, 4th ed., Chapter 2.2, "Mergesort" — includes the bottom-up (non-recursive) variant as a contrast to the top-down recursive version implemented here.

Unit tests

package com.algorithms.sorting.mergesort.classic;

import org.junit.jupiter.api.Test;

import java.util.Comparator;

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

class MergeSortTest {

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

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

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

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

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

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

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

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

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

    @Test
    void oddSizedArraySortsCorrectly() {
        Integer[] array = {9, 4, 7, 1, 3};

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

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

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

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

        assertThat(array).containsExactly(42);
    }

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

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

        assertThat(array).isEmpty();
    }

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

        MergeSort.sort(array, Comparator.reverseOrder());

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

    @Test
    void isStableElementsTiedOnTheComparatorKeepTheirOriginalRelativeOrder() {
        record Tagged(int value, int originalIndex) {
        }
        Tagged[] array = {
                new Tagged(1, 0),
                new Tagged(2, 1),
                new Tagged(1, 2),
                new Tagged(2, 3),
        };

        MergeSort.sort(array, Comparator.comparingInt(Tagged::value));

        assertThat(array).extracting(Tagged::originalIndex).containsExactly(0, 2, 1, 3);
    }

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

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

package com.algorithms.sorting.mergesort.applied;

import org.junit.jupiter.api.Test;

import java.time.Instant;

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

class ComplianceReportSortTest {

    private static final Instant WHEN = Instant.parse("2026-08-17T09:00:00Z");

    @Test
    void sortByRiskScoreDescendingOrdersHighestFirst() {
        ComplianceReportSort sorter = new ComplianceReportSort();
        FlaggedTransaction[] transactions = {
                transaction("low", 20),
                transaction("high", 90),
                transaction("mid", 55),
        };

        FlaggedTransaction[] sorted = sorter.sortByRiskScoreDescending(transactions);

        assertThat(sorted).extracting(FlaggedTransaction::transactionId).containsExactly("high", "mid", "low");
    }

    @Test
    void tiesOnRiskScorePreserveOriginalFlaggingOrder() {
        ComplianceReportSort sorter = new ComplianceReportSort();
        FlaggedTransaction[] transactions = {
                transaction("first-flagged", 70),
                transaction("second-flagged", 70),
                transaction("third-flagged", 70),
        };

        FlaggedTransaction[] sorted = sorter.sortByRiskScoreDescending(transactions);

        assertThat(sorted).extracting(FlaggedTransaction::transactionId)
                .containsExactly("first-flagged", "second-flagged", "third-flagged");
    }

    @Test
    void doesNotMutateTheInputArray() {
        ComplianceReportSort sorter = new ComplianceReportSort();
        FlaggedTransaction[] transactions = {transaction("b", 10), transaction("a", 90)};

        sorter.sortByRiskScoreDescending(transactions);

        assertThat(transactions).extracting(FlaggedTransaction::transactionId).containsExactly("b", "a");
    }

    @Test
    void rejectsNullTransactions() {
        ComplianceReportSort sorter = new ComplianceReportSort();

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

    private static FlaggedTransaction transaction(String id, int riskScore) {
        return new FlaggedTransaction(id, riskScore, WHEN);
    }
}

View full JaCoCo coverage report →