Mergesort

Mergesort is a divide-and-conquer comparison sort that recursively splits the array in half, sorts each half, then merges them. It guarantees O(n log n) on every input, and is the basis for Java's Arrays.sort on objects.

Below, a full split-and-merge trace, the two-pointer merge in detail, an iterative implementation, and guidance on when mergesort is the right choice.

1. Complexity

Best	Average	Worst	Space (Worst)
`Ω(n log n)`	`Θ(n log n)`	`O(n log n)`	`O(n)`

2. How it works

Split the array at the midpoint. Recursively sort each half. Merge the two sorted halves into one by walking both with two pointers, repeatedly taking the smaller head. The merge step is the workhorse — every element is compared and copied O(log n) times, giving the n log n total.

3. Python implementation

def mergesort(arr):
    """Top-down recursive mergesort."""
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(arr[mid:])
    return _merge(left, right)


def _merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out


print(mergesort([3, 6, 1, 8, 2, 9, 4]))  # [1, 2, 3, 4, 6, 8, 9]

4. Trade-offs

Stable — preserves the order of equal keys.
Guaranteed O(n log n) — no pathological input.
Needs O(n) auxiliary memory; not in-place.
Excellent for linked lists (no random access penalty) and external sorts.

5. Step-by-step trace

The top half of the diagram is the split phase: the array is cut at its midpoint until every piece has length one, which is trivially sorted. With seven elements the first split gives [3, 6, 1] and [8, 2, 9, 4]. The recursion depth is ⌈log₂ n⌉, here three levels. The odd length is handled naturally: the left half simply gets one element fewer than the right. The green rows are the merge phase, read bottom-up: pairs of single elements merge into sorted pairs, sorted pairs merge into runs of three and four, and the final merge produces the sorted array. Each level of the tree touches every element once, and there are about log₂ n levels, which is where n log n comes from.

6. The merge step

Merging two sorted lists of total length n takes at most n−1 comparisons. Two indices start at the heads of the runs; at each step the smaller head is appended to the output and its index advances. When one run is exhausted, the remainder of the other is copied without comparisons. Using <= rather than < when the heads are equal takes from the left run first, which preserves the original order of equal keys and makes the sort stable. Changing that single operator silently breaks stability.

7. Worked example: bottom-up, iterative mergesort

def mergesort_bottom_up(a):
    a = list(a)
    n, width = len(a), 1
    buf = [None] * n
    while width < n:
        for lo in range(0, n, 2 * width):
            mid, hi = min(lo + width, n), min(lo + 2 * width, n)
            i, j, k = lo, mid, lo
            while i < mid and j < hi:
                if a[i] <= a[j]:
                    buf[k] = a[i]; i += 1
                else:
                    buf[k] = a[j]; j += 1
                k += 1
            buf[k:hi] = a[i:mid] + a[j:hi]
        a, buf = buf, a
        width *= 2
    return a

print(mergesort_bottom_up([3, 6, 1, 8, 2, 9, 4]))  # [1, 2, 3, 4, 6, 8, 9]

The bottom-up form avoids recursion: it merges runs of width 1, then 2, then 4, swapping the roles of the array and a single reusable buffer each round. It allocates the O(n) buffer once instead of creating new lists at every recursive call, as the top-down version above does with slicing. This is the shape used for external sorting, where runs are files on disk and each pass streams them sequentially.

8. When to use it

Stability required — sorting records by a secondary key after a primary key, for example.
Predictable worst case — no adversarial input degrades it, unlike a naive quicksort.
Linked lists — merging relinks nodes, so it needs no extra array and no random access.
External and parallel sorting — sorted runs can be produced independently and merged in a k-way merge with a heap.

Prefer quicksort or introsort for in-memory arrays of primitives where stability does not matter and memory is tight; their in-place partitioning and cache behaviour usually make them faster. In Python, call sorted(), which is Timsort, a mergesort descendant. Java uses a Timsort variant for sorting object arrays for the same reason: objects often carry secondary fields, so callers expect equal keys to stay in their original order, and real data tends to contain partially sorted stretches that a run-aware mergesort exploits. For primitive arrays, where equal values are indistinguishable and stability is meaningless, Java uses a dual-pivot quicksort instead./p>

9. Pitfalls

Slicing in the recursive version copies data at every level, adding allocation overhead; pass index bounds instead in performance-sensitive code.
Deep recursion is not usually the problem (depth is log n), but very small subarrays are slow to recurse on; hybrids switch to insertion sort below a threshold such as 16 to 64 elements.
Using < instead of <= in the merge breaks stability.

See Timsort for the adaptive, run-detecting descendant, Quicksort and Heapsort for in-place alternatives, and Insertion Sort for the small-array base case.

← Back to Algorithms