Java merge sort: stable merging and one scratch buffer

Java 8+. Use a JDK that supports this release.

Use half-open ranges

Each range starts at from and ends before to. A range with fewer than two values is already sorted. The midpoint splits it into disjoint left and right ranges with no omitted index.

Merge reads two sorted inputs and writes the smaller pending value. On equality, choosing the left element first preserves the relative order of equal keys. The integer example cannot display record identity, but the tie rule is the same for a stable record comparator.

Allocate scratch storage once for the whole sort. Creating fresh subarrays at every level obscures allocation cost and makes it harder to compare the implementation with a production sort.

State mutation explicitly

sort changes the caller’s array. Copy first if readers require the original order. Returning void makes the mutation visible in the signature, but the method’s documentation must still state it.

The sample handles empty arrays and repeated values. Null is outside its contract and fails immediately when length is accessed. A public API may prefer an explicit null check for a clearer error.

Working program

import java.util.Arrays;

public class ShipmentMergeSort {
    static void sort(int[] shipmentIds) {
        split(shipmentIds, new int[shipmentIds.length], 0, shipmentIds.length);
    }
    static void split(int[] values, int[] scratch, int from, int to) {
        if (to - from < 2) return;
        int middle = from + (to - from) / 2;
        split(values, scratch, from, middle); split(values, scratch, middle, to);
        int left = from, right = middle, output = from;
        while (left < middle && right < to) {
            scratch[output++] = values[left] <= values[right] ? values[left++] : values[right++];
        }
        while (left < middle) scratch[output++] = values[left++];
        while (right < to) scratch[output++] = values[right++];
        System.arraycopy(scratch, from, values, from, to - from);
    }
    public static void main(String[] args) {
        int[] shipmentIds = {42, 11, 42, 8, 30};
        sort(shipmentIds);
        System.out.println(Arrays.toString(shipmentIds));
        int[] empty = {}; sort(empty); System.out.println(Arrays.toString(empty));
    }
}

Output

[8, 11, 30, 42, 42]
[]

Cost and design choices

Each level merges and copies O(n) elements; the split depth is O(log n). Total work is O(n log n), with O(n) scratch storage and O(log n) recursive frames.

Use the standard sorting API for ordinary application work unless custom requirements justify maintaining an algorithm. This version teaches the merge invariant, not a claim to beat library implementations.

Common Mistakes

• Do not mix inclusive and exclusive end indexes.
• Do not choose the right equal element while claiming stability.
• Do not omit scratch storage from the space bound.

Connect the contracts

Compare the boundary explained in Recursive decomposition with the assumptions made by this program.