01 The core idea: divide, sort trivially, merge

Merge sort, developed by John von Neumann in 1945, takes the divide-and-conquer pattern and applies it in the opposite order from quicksort. Where quicksort does its hard work during the split and treats the recursive calls as almost an afterthought, merge sort does almost nothing during the split and saves all the real work for putting the pieces back together.

The algorithm works in three repeated steps: split the list into two roughly equal halves, recursively sort each half independently, and then merge the two now-sorted halves back into a single sorted list. The recursion bottoms out at the trivial case — a list of zero or one elements is already sorted by definition, with nothing left to do.

Each level halves the problem — the real work happens on the way back up, merging pairs into order.

02 The merge step, in detail

Merging two already-sorted lists into one sorted list is itself a simple, linear-time operation: keep a pointer into each of the two input lists, compare the elements those pointers are currently looking at, copy the smaller one into the output, and advance that pointer. Repeat until one list runs out, then copy whatever remains of the other list straight onto the end of the output. No backtracking, no re-comparison of elements already placed — every element is looked at exactly once during a merge.

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])   # copy whatever's left over
    result.extend(right[j:])
    return result

That <= comparison rather than a strict < is a small detail with a large consequence — it’s what guarantees that when two elements are equal, the one from the left half is placed first, preserving the original relative order between equal elements.

03 Code in Python, Java, and OCaml

def merge_sort(items):
    if len(items) <= 1:
        return items

    mid = len(items) // 2
    left = merge_sort(items[:mid])
    right = merge_sort(items[mid:])
    return merge(left, right)

static int[] mergeSort(int[] items) {
    if (items.length <= 1) return items;

    int mid = items.length / 2;
    int[] left  = mergeSort(Arrays.copyOfRange(items, 0, mid));
    int[] right = mergeSort(Arrays.copyOfRange(items, mid, items.length));
    return merge(left, right);
}

let rec merge left right =
  match left, right with
  | [], r -> r
  | l, [] -> l
  | lh :: lt, rh :: rt ->
    if lh <= rh then lh :: merge lt right
    else rh :: merge left rt

let rec merge_sort = function
  | [] | [_] as lst -> lst
  | lst ->
    let mid = List.length lst / 2 in
    let left, right = split_at mid lst in
    merge (merge_sort left) (merge_sort right)

04 Why merge sort’s complexity never gets worse

Merge sort’s reliability comes from the fact that splitting a list in half doesn’t depend on the data at all — unlike quicksort, where an unlucky pivot can produce a badly unbalanced split, merge sort’s split point is always the literal midpoint, every single time. That guarantees the recursion tree is always perfectly balanced, with exactly log₂ n levels no matter the input. At each level, the total cost of merging is proportional to n, giving the same n log n total work in the best, average, and worst case.

05 The memory cost nobody mentions enough

That guaranteed performance has a price: a standard merge sort implementation needs auxiliary memory proportional to n to hold the temporary arrays created during merging, whereas quicksort’s partitioning happens in place, using only a small constant amount of extra memory regardless of input size. For very large datasets — particularly ones close to the limits of available memory — that difference is not a minor footnote; it can be the deciding factor in which algorithm is even feasible to use.

06 Stability — merge sort’s quiet advantage

A sorting algorithm is called stable if it preserves the relative order of elements that compare as equal. Merge sort is naturally stable, as long as the merge step always favors the left half when elements tie — exactly the behavior of the <= comparison shown earlier. This matters in any situation where you’re sorting structured data by one field while wanting ties on that field to retain their original order. Quicksort, by contrast, has no such guarantee unless specifically modified to track original positions.

07 When merge sort beats quicksort in practice

• Stability is a hard requirement. If equal elements must keep their original relative order, merge sort’s natural stability avoids extra engineering that quicksort would need.
• Worst-case guarantees actually matter. Real-time systems, or any context where a single slow operation is unacceptable regardless of how rare it is, benefit from merge sort’s complete absence of a pathological case.
• Sorting linked lists. Merge sort’s merge step doesn’t need random access to elements the way quicksort’s partitioning benefits from — it works naturally and efficiently on linked-list structures where quicksort’s usual advantages largely disappear.
• External sorting. When data is too large to fit in memory and must be sorted in chunks read from disk, merge sort’s structure — sort small chunks, then repeatedly merge them — maps directly onto that problem and is the basis of most external-sort implementations.