Merge Sort:Stable Divide-and-Conquer When You Can Afford the Extra Array

A billing export sorts invoices by customer id. Two rows for the same customer must stay in file order — the first filing, then the resubmit. An intern copies a partition sort because a second array is “waste.” Equal keys swap. Finance sees the resubmit first. Nobody wrote a bad Comparator. They picked a procedure that does not keep equal keys in original order, and they spent the saved memory on a ticket.

Merge sort splits the range, sorts each half, and merges two sorted runs into a new array. The extra memory is the price of a guaranteed O(n log n) bound and a merge that can keep ties in original order. The recursion is how you obtain the runs. The merge is the procedure.

This post is that split-and-merge. Families, the glossary, and the catalog live on the Algorithms Roadmap. Here we only care about two sorted slices, the walk that consumes them from the left, and why you almost never hand-roll this for objects in Java.

Two sorted runs become one

Divide-and-conquer, used not lectured: if a slice has length 0 or 1 it is already sorted. Otherwise split at mid, sort the left half, sort the right half, then merge.

Merge is sequential. You hold an index in each run. The smaller head goes into the output. On a tie you take the left head, so equal keys stay in the order they had before this merge — and therefore in the order they had in the original array, because both halves were sorted the same way.

left  (already sorted):  3, 8, 8, 12
right (already sorted):  5, 8, 20

take 3 (left)
take 5 (right)
take 8 (left — tie with right's 8, left wins)
take 8 (left — another left 8 still ≤ right's 8)
take 8 (right)
take 12
take 20

merged:  3, 5, 8, 8, 8, 12, 20

The three 8s kept left-before-right. That is the whole stability argument. There is no clever index formula. There is a copy into an auxiliary array (or a merge into a fresh one) because the output cannot overwrite a head you have not consumed yet.

Note: Allocate the auxiliary array once for the whole sort and reuse it. Allocating a new buffer inside every merge is still O(n) extra in the textbook sense and a garbage storm in a JVM.

A walked pass: [38, 27, 43, 3] then a tie

Four keys, split until the slices are trivial, merge on the way back. Mid is lo + (hi - lo) / 2 on a half-open [lo, hi), same overflow-safe mid as binary search.

a = [38, 27, 43, 3]
     0   1   2   3     [lo, hi) = [0, 4)

split [0, 4) at mid=2
  left  [0, 2) = [38, 27]
  right [2, 4) = [43,  3]

split [0, 2) at mid=1  → [38] | [27]
merge [38] and [27]    → [27, 38]

split [2, 4) at mid=3  → [43] | [3]
merge [43] and [3]     → [3, 43]

merge [27, 38] and [3, 43]:
  3 < 27 → 3
  27 < 43 → 27
  38 < 43 → 38
  leftover 43
  → [3, 27, 38, 43]

Same shape with a tie. Original file order is the subscript:

(value, file order):  5₀, 2₁, 5₂, 1₃

after the tree of merges:
  [2₁, 5₀] merged with [1₃, 5₂]
  1₃, then 2₁, then 5₀ before 5₂  (tie: left run wins)
  → 1₃, 2₁, 5₀, 5₂

5₀ stays ahead of 5₂. A partition that swaps across the pivot does not have to. That contrast is quicksort: it rearranges in place, and it is not the stable default.

Java sketch

Half-open range, one aux, left-on-tie (<=). The sketch sorts int[]; objects are the same loop with compare <= 0.

static void mergeSort(int[] a) {
    int[] aux = new int[a.length];
    sort(a, aux, 0, a.length);
}

static void sort(int[] a, int[] aux, int lo, int hi) {
    if (hi - lo <= 1) {
        return;
    }
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid, hi);
    merge(a, aux, lo, mid, hi);
}

static void merge(int[] a, int[] aux, int lo, int mid, int hi) {
    for (int t = lo; t < hi; t++) {
        aux[t] = a[t];
    }
    int i = lo;
    int j = mid;
    for (int k = lo; k < hi; k++) {
        if (i >= mid) {
            a[k] = aux[j++];
        } else if (j >= hi) {
            a[k] = aux[i++];
        } else if (aux[i] <= aux[j]) {
            a[k] = aux[i++];
        } else {
            a[k] = aux[j++];
        }
    }
}

Empty and singleton inputs return immediately. The depth of the recursion is Θ(log n) splits; each level copies every element once through merge, so the comparison work is Θ(n log n) on every input — already-sorted, reversed, or hostile.

An iterative bottom-up version is the same merge with a growing run width (1, 2, 4, …) instead of a call stack. Same extra array. Same left-on-tie rule. External sort is that idea at disk scale: the runs live in files, and you merge k of them at a time.

Extra memory is the price

Quicksort’s selling point is in-place partition. Merge sort’s selling point is the opposite trade: you buy a linear auxiliary buffer, and in return you get a bound that does not depend on pivot luck and a merge that can be stable.

You need	This procedure	Not this procedure
Equal keys in original order	Merge (left on tie)	A partition that may swap twins
Hostile input still O(n log n)	Merge sort, every level	A bad pivot policy
No second array	Quicksort / heapsort	Textbook merge sort

Skipping the aux array to “save memory” and then losing file order on equal customer ids is how the billing export became an incident. If the product requires stability, the extra array is not optional decoration. If the product does not, and RAM is the constraint, pick a different sort.

What object Arrays.sort actually runs is not this recursive textbook. It is Timsort: identify already-sorted runs, then merge those runs. Same merge primitive. Different split. Nearly-sorted input stays cheap because you do not break runs you already have. Do not reimplement that.

Complexity

The procedure always splits to the bottom and always merges every level.

Time	Θ(n log n) comparisons, every input
Extra space	O(n) auxiliary plus O(log n) recursion
Stable	Yes, if the merge takes the left run on a tie
In-place	No, in the usual form

Worst case, best case, and average case are the same leading term. That is the thing you paid the extra array for. A linked-list merge sort can splice nodes instead of copying into aux; random-access arrays do not get that layout for free, and this series is not re-teaching lists.

When not to use textbook merge sort

Skip the hand-rolled recursion when:

• The data already fits, and it is objects. Call Arrays.sort / List.sort. That path is Timsort, not this tree of splits.
• You cannot afford a second array and you do not need stability. Partition in place, or heapsort. Measure the RAM, do not cargo-cult “merge is safer” into an OOM.
• n is tiny. A short insertion pass (and Timsort’s tiny-run policy) beats a full divide tree. Five invoices do not need a sketch from this page.
• The file does not fit in RAM. Splitting an int[] you could not allocate is not a plan. That job is k-way merge of on-disk runs — external sort.

Do not merge-sort on every lookup so a later binary search is “legal.” Same cargo-cult the hub names: you paid O(n log n) to avoid an O(n) scan. Sort when the set is built, then query.

JDK: you rarely hand-roll this for objects

There is no java.util.MergeSort. The library you call is the sort:

• Object arrays and lists: Arrays.sort / List.sort / Collections.sort — Timsort, stable, run-merging, not the recursive sketch above.
• Primitive arrays (int[], long[], …): Dual-Pivot Quicksort. Fast. Not a stability promise.

Object sort → the JDK call. Hand-roll the sketch when you are learning the merge, merging two already-sorted arrays you already hold, or writing a specialized run merge the JDK does not expose.

record Invoice(int customerId, int fileSeq) {}

Invoice[] rows = { /* ... */ };
Arrays.sort(rows, Comparator.comparingInt(Invoice::customerId));
// stable: equal customerId keeps file order

int[] ids = {38, 27, 43, 3};
Arrays.sort(ids); // primitive: dual-pivot quicksort, not this post

If you need a stable order on primitives, do not start by pasting textbook merge sort into production. Pair the value with its original index, or sort boxed keys, or keep objects. The Timsort post owns what the object path already does for you.

Note: Arrays.sort on objects does not require you to prove the array is unsorted. It also does not require you to implement merge. A custom mergeSort on the billing path is a review question, not a default.

Cheat sheet

Job:        sort a range; keep equal keys in original order if the merge takes left
Split:      mid = lo + (hi - lo) / 2 on [lo, hi); recurse; then merge
Merge:      two sorted runs → one; on tie, consume the left head
Aux:        one O(n) array, allocated once, reused
Time:       Θ(n log n) always
Space:      O(n) extra (usual array form)
Not this:   in-place partition (quicksort); object Arrays.sort (Timsort)
JDK:        Arrays.sort / List.sort for objects; do not hand-roll the default

Do:

• Take the left run on <= (or compare <= 0) if the product needs original order among ties.
• Allocate aux once; reuse it on every merge.
• Call the JDK for object arrays; treat this sketch as the merge you need to understand, not the one you ship.

Don’t:

• Drop the extra array and keep calling the result merge sort.
• Use aux[i] < aux[j] on a tie and then promise file order.
• Hand-roll recursive merge sort for Invoice[] when Arrays.sort already runs a stable merge of runs.
• Pretend primitive Arrays.sort is this algorithm.

Wrap-up

Merge sort is a guaranteed O(n log n) sort whose combine step is “merge two sorted runs.” The extra array is how the output is built without eating an unconsumed head. Take the left run on a tie and equal keys keep their original order. Quicksort partitions in place and does not make that promise; Timsort is what object Arrays.sort actually runs — a merge of natural runs, not a textbook recursion you should paste into the billing export.

Use the sketch to learn the merge, and to combine two runs you already have. Use the JDK for objects. When RAM cannot hold the file, stop splitting an array you never allocated — that is a different post.

Next optional step in the series Partition in place, and why the pivot policy is the algorithm. Quicksort: Partition in Place →