Merge Sort — Specification¶

Algorithm Specification — Reference Standard

Source: Knuth, TAOCP Vol. 3 — Section 5.2.4 (sorting by merging) Source: CLRS, Introduction to Algorithms — Chapter 2.3 (Merge Sort) and Chapter 4 (Master Theorem) Source: TimSort original spec

Table of Contents¶

1. Algorithm Reference
2. API / Interface Reference
3. Core Rules and Behavioral Specification
4. Schema / Parameters Reference
5. Behavioral Specification
6. Edge Cases
7. Complexity Compatibility Matrix
8. Reference Implementations
9. Compliance & Best Practices Checklist
10. Related Documentation

1. Algorithm Reference¶

2. API / Interface Reference¶

Standard Function Signature¶

MERGE_SORT(A: array of T, cmp: (T, T) → int) → array of T  [or in-place]
  Sorts A using cmp.

Postcondition:
  ∀ i ∈ [0, n-2]: cmp(A[i], A[i+1]) ≤ 0
  AND A is a permutation of the original input.
  AND for any two equal elements, original order is preserved (stability).

Language-Specific Implementations¶

Pattern: All major stable sorts in modern runtimes are based on Merge Sort (TimSort or vanilla).

3. Core Rules and Behavioral Specification¶

Rule 1: Recursive Structure (Top-Down)¶

CLRS §2.3: "If the input length is greater than one, divide it in half, recursively sort the two halves, and then merge them."

# ✅ Correct
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))

# ❌ Incorrect — wrong base case
def merge_sort(arr):
    if len(arr) == 0:  # missing single-element case
        return arr
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
    # infinite recursion on single-element arrays

Rule 2: Stability via <= in Merge¶

Specification: The merge step must use <= (not <) to preserve stability.

# ✅ Correct — stable
if left[i] <= right[j]:
    result.append(left[i]); i += 1

# ❌ Incorrect — unstable
if left[i] < right[j]:
    result.append(left[i]); i += 1
# When left[i] == right[j], takes from right first → reverses original order

Rule 3: Avoid Integer Overflow in Mid Calculation¶

CLRS errata: (low + high) / 2 overflows for arrays of size > 2³¹/2 = ~10⁹ on 32-bit ints.

# ✅ Correct — overflow-safe
mid = low + (high - low) / 2

# ❌ Incorrect — overflow risk
mid = (low + high) / 2

Rule 4: Single Auxiliary Buffer for Performance¶

Sedgewick Algorithms 4ed §2.2: "Allocating the auxiliary array as a local variable in the merge() method is a wasteful practice... allocate space for the auxiliary array in the public sort() method just once."

# ✅ Correct — one allocation
def merge_sort(arr):
    aux = [0] * len(arr)
    _sort(arr, aux, 0, len(arr) - 1)

# ❌ Incorrect — allocates per recursive call
def merge_sort(arr):
    if len(arr) <= 1: return arr
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
    # [:mid] and [mid:] create new arrays at every recursion level

Rule 5: Comparator Must Define a Total Order¶

Java Comparator contract: "The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) ... and ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0."

Violating these causes undefined behavior (may infinite-loop, may produce wrong order).

4. Schema / Parameters Reference¶

Returns: Either the sorted array (functional style) or void (in-place mutation). Convention varies by language.

5. Behavioral Specification¶

Normal Operation¶

For input A of length n ≥ 2:

1. Split A into A_left (first ⌈n/2⌉ elements) and A_right (last ⌊n/2⌋ elements).
2. Recursively merge_sort(A_left) → sorted L.
3. Recursively merge_sort(A_right) → sorted R.
4. Merge L and R into output, taking smaller of L[i] and R[j] at each step (taking from L on ties).

For inputs of length 0 or 1: return immediately, no work done.

Documented Limitations¶

Error / Failure Conditions¶

6. Edge Cases¶

7. Complexity Compatibility Matrix¶

Comparator Compatibility¶

8. Reference Implementations¶

CLRS Reference (Sentinel-Based Merge)¶

MERGE-SORT(A, p, r):
  if p < r:
      q = ⌊(p + r) / 2⌋
      MERGE-SORT(A, p, q)
      MERGE-SORT(A, q + 1, r)
      MERGE(A, p, q, r)

MERGE(A, p, q, r):
  n₁ = q - p + 1
  n₂ = r - q
  let L[1..n₁ + 1] and R[1..n₂ + 1] be new arrays
  for i = 1 to n₁: L[i] = A[p + i - 1]
  for j = 1 to n₂: R[j] = A[q + j]
  L[n₁ + 1] = ∞
  R[n₂ + 1] = ∞
  i = 1; j = 1
  for k = p to r:
      if L[i] ≤ R[j]:
          A[k] = L[i]; i = i + 1
      else:
          A[k] = R[j]; j = j + 1

Sedgewick Reference (No Sentinels)¶

Java¶

public class MergeSort {
    private static int[] aux;

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

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

    private static void merge(int[] a, int lo, int mid, int hi) {
        for (int k = lo; k <= hi; k++) aux[k] = a[k];
        int i = lo, j = mid + 1;
        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[j] < aux[i]) a[k] = aux[j++];
            else                      a[k] = aux[i++];
        }
    }
}

TimSort Reference¶

See TimSort original specification for the complete algorithm including: - Run detection - minrun calculation - Merge stack invariants (A > B + C and B > C) - Galloping mode

9. Compliance & Best Practices Checklist¶

• Uses <= (not <) in merge to preserve stability
• Uses mid = lo + (hi - lo) / 2 to avoid integer overflow
• Allocates single auxiliary buffer in the public entry point, not per recursive call
• Switches to Insertion Sort for subarrays smaller than ~16 elements (cutoff)
• Skips merge step when arr[mid] <= arr[mid+1] (already sorted detection)
• Handles empty array and single element as base cases
• Comparator (if custom) defines a total order
• Documents mutation vs. return new array convention
• For huge n, uses bottom-up iterative to avoid stack overflow
• For data > RAM, uses external merge sort with k-way merge
• For linked lists, uses slow/fast pointer to find midpoint (no array conversion)

10. Related Documentation¶

Specification Notes: - Merge Sort is the only standard sort that's both stable and worst-case O(n log n). This combination is why it (or its hybrid TimSort) dominates production runtimes. - For arrays in dense numeric workloads, Quick Sort variants (Pdqsort, Dual-Pivot QS) often beat Merge Sort due to cache locality. - For object arrays with comparator-based sort, TimSort dominates because it's stable, predictable, and adaptive. - For external sort (data > RAM), Merge Sort is the de facto standard — there is no practical competitor. - The <= vs < choice in the merge step is the single most important detail — it's the difference between stable and unstable.