Merge Sort

Merge sort splits the array in half, sorts each half, and merges the two sorted halves back together. It is O(n log n) in every case and it is stable — and it is the algorithm Java uses to sort objects.

The shape

        [ 5  3  8  1 ]
        /            \
    [ 5  3 ]        [ 8  1 ]        divide
     /    \          /    \
   [5]   [3]       [8]   [1]        single elements are sorted by definition
     \    /          \    /
    [ 3  5 ]        [ 1  8 ]        merge
        \            /
        [ 1  3  5  8 ]

log n levels of splitting, O(n) work merging at each level: O(n log n). And because it always splits exactly in half, that holds for every input — there is no bad case.

The top level

    /** Divide in half, sort each half, merge. O(n log n) time, O(n) space, stable. */
    public static void mergeSort(int[] a) {
        if (a.length < 2) {
            return;
        }
        // Allocated ONCE, here, and reused by every level of the recursion. Allocating inside
        // merge() instead is the usual version and it churns O(n log n) arrays for no reason.
        int[] buffer = new int[a.length];
        mergeSort(a, buffer, 0, a.length - 1);
    }

The buffer is the detail most implementations get wrong. Allocating a fresh temporary inside merge is the textbook version, and it allocates on the order of n log n arrays' worth of memory for a job that needs one. Same complexity on paper, considerably more garbage collection in practice.

The early exit

        // Already in order - skip the merge entirely. Cheap to check, and it makes an
        // already-sorted array O(n log n) with no data movement at all.
        if (a[mid] <= a[mid + 1]) {
            return;
        }

If the largest element of the left half is already ≤ the smallest of the right half, the two halves are in order and merging would copy every element to where it already is. One comparison skips the whole step. On sorted or nearly-sorted input — extremely common in real data — this is a large saving for almost no code.

The merge, and where stability lives

        int left = low;
        int right = mid + 1;
        for (int i = low; i <= high; i++) {
            if (left > mid) {
                a[i] = buffer[right++];
            } else if (right > high) {
                a[i] = buffer[left++];
            } else if (buffer[right] < buffer[left]) {
                a[i] = buffer[right++];
            } else {
                // <= keeps the LEFT element when they are equal. That single choice is what
                // makes this sort stable; flipping it to < silently breaks stability.
                a[i] = buffer[left++];
            }
        }

Four branches: left exhausted, right exhausted, right is smaller, otherwise take left. The two exhaustion checks come first so the comparison never reads past the end of either half.

Stability, and why it matters

A sort is stable if elements that compare equal keep their original relative order. That last else is where it comes from: on a tie, take from the left half — the one that came first.

Flip the comparison to <= and everything still sorts correctly. Stability is simply gone, and no test that only checks "is it sorted" will ever notice.

It matters whenever you sort twice. Sort employees by name, then by department: with a stable sort, people within a department are still in name order. With an unstable one, that second sort scrambles the first. It is also why quick sort — which is not stable — cannot be used where this is needed.

Merge sort against quick sort

Quick sort usually wins on wall clock despite identical complexity, because it sorts in place and its memory access is cache-friendly, while merge sort copies between two arrays. Merge sort wins when you need a guarantee or stability.

This is exactly why Java ships both: Arrays.sort on primitives is a dual-pivot quicksort, and on objects it is TimSort, a merge sort. The reason is stability — two equal ints are indistinguishable, so stability is meaningless for primitives, whereas two objects that compare equal are still different objects and their order is observable.

Testing it properly

        int[][] cases = {
            {},
            {1},
            {2, 1},
            {5, 3, 8, 1, 9, 2, 7},
            {1, 2, 3, 4, 5},          // already sorted - quicksort's classic worst case
            {5, 4, 3, 2, 1},          // reversed
            {7, 7, 7, 7},             // all equal
            {3, -1, 0, -9, 4},        // negatives
        };

Each case is a real failure mode: empty and single-element arrays break naive base cases, all-equal input breaks bad partitioning, and reversed input is where a fragile implementation degrades. Every one is checked against Arrays.sort, plus a 5,000-element pseudo-random array — deterministic, so a failure is reproducible.

Where merge sort is the only option

Sorting a linked list. Quick sort needs random access to partition; merge sort only ever walks forwards, and merging two sorted lists is pure pointer manipulation with no extra memory at all.

Sorting data larger than memory. External merge sort reads chunks that fit in RAM, sorts them, writes them out, and merges the sorted runs. The merge step only needs one element from each run at a time, which is what makes it work on a file bigger than the machine.

What to remember

• O(n log n) in every case — no bad input.
• Stable, and the stability is one <= in the merge.
• O(n) extra space; allocate the buffer once.
• The a[mid] <= a[mid + 1] check makes sorted input nearly free.
• Java uses it for objects, and quick sort for primitives — because of stability.
• The right choice for linked lists and for data that does not fit in memory.