Merge Sort

Merge sort is the textbook divide-and-conquer sorting algorithm: split the array in half, recursively sort each half, then merge the two sorted halves into one sorted output. It runs in O(n log n) guaranteed (worst, average, and best case all the same), is stable (preserves the relative order of equal elements), and is the algorithm of choice when you need predictable performance, when sorting linked lists, or when sorting data too large to fit in memory (external merge sort).

1. Intuition — Sorting With Two Friends

You have a shuffled deck of 52 cards.

• You split it in half: 26 + 26.
• You hand each half to a friend and ask them to sort it.
• Each friend, faced with 26 unsorted cards, splits their half and asks two more friends to sort 13 each. (And so on, recursively, until someone is handed just 1 card — which is trivially “sorted.”)
• Once both friends hand you back their sorted halves, you merge them: hold both stacks face-up; repeatedly take whichever top card is smaller and place it on your output stack. When one stack runs out, dump the other on top.

The recursion is the “divide” — splitting until trivial. The merge is the “conquer” — combining solutions. The merging step is the cleverness; the recursion is just bookkeeping.

2. The Tiny Worked Example (n = 8)

Sort [5, 2, 8, 1, 9, 3, 7, 4].

                    [5, 2, 8, 1, 9, 3, 7, 4]
                   /                          \
               split into                  split into
              [5, 2, 8, 1]                [9, 3, 7, 4]
              /          \                /          \
           [5,2]        [8,1]          [9,3]        [7,4]
           /  \         /  \           /  \         /  \
          [5] [2]     [8] [1]        [9] [3]     [7] [4]
           \  /        \  /           \  /        \  /
           [2,5]       [1,8]          [3,9]       [4,7]
              \          /                \          /
              [1, 2, 5, 8]                [3, 4, 7, 9]
                          \              /
                           [1, 2, 3, 4, 5, 7, 8, 9]

The merge step in detail for [1,2,5,8] + [3,4,7,9]:

Left ptr	Right ptr	Take	Output so far
1	3	1 (left)	[1]
2	3	2 (left)	[1,2]
5	3	3 (right)	[1,2,3]
5	4	4 (right)	[1,2,3,4]
5	7	5 (left)	[1,2,3,4,5]
8	7	7 (right)	[1,2,3,4,5,7]
8	9	8 (left)	[1,2,3,4,5,7,8]
(done)	9	9 (right)	[1,2,3,4,5,7,8,9]

Each merge step does one comparison and one copy. To merge two halves of total size n, the merge step does at most n - 1 comparisons and exactly n copies — O(n) work.

3. Pseudocode

merge_sort(arr):
    n := length(arr)
    if n <= 1:
        return arr                              # base case
    mid := n / 2
    left  := merge_sort(arr[0..mid])           # recurse
    right := merge_sort(arr[mid..n])
    return merge(left, right)

merge(left, right):
    result := empty list
    i := 0; j := 0
    while i < length(left) and j < length(right):
        if left[i] <= right[j]:                 # <= keeps it stable
            append left[i] to result
            i := i + 1
        else:
            append right[j] to result
            j := j + 1
    append remaining left[i..] to result
    append remaining right[j..] to result
    return result

The <= (rather than <) in the comparison is what makes the sort stable: when two elements are equal, the one from the left (earlier in original) goes first.

4. Python Implementation

4.1 Functional / Out-of-Place

def merge_sort(arr: list[int]) -> list[int]:
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
 
def merge(left: list[int], right: list[int]) -> list[int]:
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:        # <= for stability
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])             # append any leftovers
    result.extend(right[j:])
    return result

4.2 In-Place (with auxiliary buffer)

The functional version copies many subarrays. A cleaner version uses indices into the original array and a single auxiliary buffer:

def merge_sort_inplace(arr: list[int]) -> None:
    aux = arr.copy()                              # one global aux buffer
    _msort(arr, aux, 0, len(arr) - 1)
 
def _msort(arr, aux, lo, hi):
    if lo >= hi: return
    mid = (lo + hi) // 2
    _msort(arr, aux, lo, mid)
    _msort(arr, aux, mid + 1, hi)
    _merge(arr, aux, lo, mid, hi)
 
def _merge(arr, aux, lo, mid, hi):
    for k in range(lo, hi + 1):                   # copy to aux
        aux[k] = arr[k]
    i, j = lo, mid + 1
    for k in range(lo, hi + 1):
        if   i > mid:               arr[k] = aux[j]; j += 1
        elif j > hi:                arr[k] = aux[i]; i += 1
        elif aux[j] < aux[i]:       arr[k] = aux[j]; j += 1   # < (not <=) for stability with this orientation
        else:                       arr[k] = aux[i]; i += 1

This is the version most textbooks (CLRS, Sedgewick) actually present. It still uses O(n) extra space for aux, but it does so once instead of allocating fresh sub-arrays at every recursion level.

5. Complexity Analysis

5.1 Time

The recurrence is:

T(n) = 2 · T(n/2) + Θ(n)

Two subproblems of half size + linear merge work. By the Master Theorem (Case 2), this resolves to T(n) = Θ(n log n).

By hand: at each “level” of the recursion tree, the total merge work is Θ(n) (regardless of how many subproblems there are at that level — each is smaller, but there are more). There are log₂ n levels. So total work = n × log₂ n = Θ(n log n).

This is the same in worst, average, and best case. Merge sort doesn’t care about input order — every input takes the same number of operations (modulo a few comparisons that get short-circuited).

5.2 Space

• Auxiliary space: O(n) — the merge buffer. This is the algorithm’s main weakness.
• Recursion depth: O(log n) — the call stack.
• Total auxiliary: O(n) (the buffer dominates).

A genuine in-place merge sort does exist. Block sort (also called block merge sort), the practical algorithm proposed by Pok-Son Kim and Arne Kutzner in 2008, is a stable, in-place sort that achieves O(n log n) worst-case time using only O(1) auxiliary memory (in the transdichotomous model — i.e. constant extra stack and heap space beyond the input array), per the Block sort article. It works by partitioning the data into blocks of size roughly √n, then merging blocks using rotations rather than a scratch buffer — trading the O(n) buffer for a more elaborate in-array shuffling. The catch is in the constants and the engineering: block sort is markedly harder to implement and parallelize than ordinary merge sort, and it does not exploit pre-sorted runs as finely as Tim Sort does. So although it disproves the old folk belief that “stable + in-place + O(n log n) is impossible all at once,” it sees little production use. In everyday practice, accepting the O(n) auxiliary buffer is the right trade — the buffer is cheap and the merge loop stays simple and cache-friendly. (The WikiSort and GrailSort libraries are open-source implementations of the block-sort idea.)

6. The “Stable Sort” Property — Why It Matters

A sort is stable if equal elements appear in their original relative order in the output.

Example: sort [("Alice", 30), ("Bob", 25), ("Carol", 30)] by age.

• A stable sort: [("Bob", 25), ("Alice", 30), ("Carol", 30)] — Alice before Carol, as in input.
• An unstable sort might swap Alice and Carol because they tie.

Why stability is useful: you can sort by secondary key first, then by primary key — the result is sorted by primary, with secondary as tiebreaker. This is a common trick when your sort comparator is complex. Quicksort is not stable; merge sort is.

In Python, sorted() and list.sort() are stable (they use Tim Sort, a hybrid based on merge sort).

Relationship to Timsort. Timsort — devised by Tim Peters in 2002 for CPython, and since adopted as the default object-array sort in Java (since Java 7), on Android, in V8, in Swift, and elsewhere (Timsort, Wikipedia) — is best understood as production-hardened, adaptive merge sort. It keeps merge sort’s two load-bearing properties (stability and the O(n log n) worst case) and bolts on three engineering wins. First, run detection: it scans for maximal already-ordered “runs” (ascending, or strictly descending which it reverses in place) and uses them as the natural base segments instead of recursing all the way down to singletons — so nearly-sorted input is sorted in close to O(n). Second, a minrun floor: short runs are extended to a minimum length (typically 32–64) using binary insertion sort, and minrun is chosen so the run count is near a power of two, keeping the bottom-up merges balanced. Third, galloping mode: when merging two runs and one keeps “winning” the comparison, Timsort switches from one-at-a-time comparison to an exponential (galloping) search to copy a whole block at once, which is a large speedup when runs are very unequal in length. The merge itself uses temporary storage proportional to the smaller of the two runs, so its auxiliary space is O(n) worst-case but often far less in practice. The takeaway: plain merge sort is the conceptual core; Timsort is what you actually want when sorting real-world, partially-ordered data with a stable comparator.

7. When To Use Merge Sort

7.1 Use it when:

• You need guaranteed O(n log n) performance — no O(n²) worst case (Quicksort has one).
• You need a stable sort.
• You’re sorting a linked list — merge sort is natural here (no random access needed); quicksort on a linked list is awkward.
• You’re sorting larger-than-memory data — external merge sort streams chunks in/out; quicksort can’t.
• You want predictable behavior — merge sort’s running time is deterministic regardless of input.

7.2 Use Quicksort (or Tim Sort) instead when:

• You need in-place sorting (memory-constrained).
• Average case matters more than worst case.
• The hidden constants matter — quicksort’s inner loop is tighter than merge sort’s; in practice quicksort is often 2-3× faster on random data despite the same asymptotic class.

8. External Merge Sort — Sorting Data Larger Than RAM

This is a frequent interview question for systems-oriented roles. Also relevant in System Design Interview Framework discussions of large-scale data processing.

Problem: sort a 100 GB file on a machine with 4 GB of RAM.

Algorithm:

1. Run formation. Read 4 GB at a time, sort in memory (using any fast sort), write to a temp file. Repeat until all 100 GB is split into ~25 sorted “runs.”
2. Multi-way merge. Open all 25 sorted runs, do a k-way merge using a min-heap (one entry per run, smallest atop). Pop smallest, write to output, refill from that run. O(n log k) where k is the run count.

This is exactly what databases and Hadoop’s MapReduce shuffle do under the hood for sorting and grouping.

9. Bottom-Up (Iterative) Merge Sort

Recursion is the natural way to express merge sort, but it can be done iteratively — useful when recursion is expensive (deep call stacks) or unavailable.

def merge_sort_iterative(arr: list[int]) -> list[int]:
    n = len(arr)
    width = 1
    while width < n:
        for i in range(0, n, 2 * width):
            left  = arr[i : i + width]
            right = arr[i + width : i + 2 * width]
            arr[i : i + 2 * width] = merge(left, right)
        width *= 2
    return arr

Same O(n log n) time, but no recursion stack.

10. Counting Inversions — A Classic Merge Sort Trick

An inversion in an array is a pair (i, j) with i < j but arr[i] > arr[j] — i.e., a “wrong-order” pair. The number of inversions measures how unsorted the array is.

Naive count: O(n²), check every pair.

Merge-sort count: O(n log n). During the merge step, every time you take an element from the right subarray while elements remain in the left, those remaining left elements all form inversions with this right element.

def count_inversions(arr):
    def msort(a):
        if len(a) <= 1: return a, 0
        mid = len(a) // 2
        left,  inv_l = msort(a[:mid])
        right, inv_r = msort(a[mid:])
        merged, inv_m = merge_count(left, right)
        return merged, inv_l + inv_r + inv_m
 
    def merge_count(l, r):
        out, inv = [], 0
        i = j = 0
        while i < len(l) and j < len(r):
            if l[i] <= r[j]:
                out.append(l[i]); i += 1
            else:
                out.append(r[j]); j += 1
                inv += len(l) - i              # KEY LINE
        out.extend(l[i:]); out.extend(r[j:])
        return out, inv
 
    return msort(arr)[1]

This problem appears regularly in coding interviews and is a subtle test of understanding merge sort, not just memorizing it.

11. Diagram — Recursion Tree

flowchart TD
  N["[5,2,8,1,9,3,7,4]<br/>n=8"]
  N --> L["[5,2,8,1]<br/>n=4"]
  N --> R["[9,3,7,4]<br/>n=4"]
  L --> LL["[5,2]"] 
  L --> LR["[8,1]"]
  R --> RL["[9,3]"]
  R --> RR["[7,4]"]
  LL --> LLL["[5]"] 
  LL --> LLR["[2]"]
  LR --> LRL["[8]"]
  LR --> LRR["[1]"]
  RL --> RLL["[9]"]
  RL --> RLR["[3]"]
  RR --> RRL["[7]"]
  RR --> RRR["[4]"]

What this diagram shows. The recursion tree for n=8. At each level, total work is Θ(n) for the merges; tree height is log₂ n. Total work = n · log₂ n = O(n log n). The base-case singleton arrays are trivially sorted; the real work happens on the way back up the tree, in the merge steps.

12. Pitfalls

12.1 Forgetting the Base Case

if len(arr) <= 1: return arr — without this, you recurse forever on a 1-element subarray and stack overflow.

12.2 Using < Instead of <= (or vice versa)

The comparison in merge controls stability. <= (in the “left wins ties” formulation) gives stable; < gives unstable. Both produce a sorted output, but with different relative orders for equal elements.

12.3 Allocating Aux Per-Call

Allocating a fresh aux buffer at every recursive call is O(n log n) allocations. Allocate one aux buffer at the top level and pass it through.

12.4 Off-by-One in Index Math

mid = (lo + hi) // 2, then recurse on [lo, mid] and [mid+1, hi] (closed) — note mid+1, not mid. Easy to write [lo, mid] and [mid, hi] and have mid processed twice. Check bounds carefully.

12.5 Calling It “Quicksort” or vice versa

It happens. Merge sort splits down to singletons then merges; quick sort partitions around a pivot then recurses. The names are not interchangeable.

13. Quick Comparison Table

Property	Merge Sort	Quicksort	Heap Sort	Tim Sort
Worst time	O(n log n)	O(n²)	O(n log n)	O(n log n)
Average time	O(n log n)	O(n log n)	O(n log n)	O(n log n)
Best time	O(n log n)	O(n log n)	O(n log n)	O(n) (sorted input)
Auxiliary space	O(n)	O(log n)	O(1)	O(n)
Stable?	✅	❌	❌	✅
In-place?	❌ (typical)	✅	✅	❌
Adaptive?	❌	❌	❌	✅

14. Open Questions

• Is the constant overhead of “natural” merge sort (which exploits already-sorted runs) close enough to Tim sort that the latter is unnecessary? In practice no — Tim sort has been refined for decades.
• When does external merge sort lose to “sort then merge” with a different in-memory algorithm? Usually it doesn’t — external merge sort is provably optimal in I/O complexity.

15. See Also

• Quicksort — the in-place, average-case-faster D&C alternative
• Heap Sort — guaranteed O(n log n), in-place, but unstable
• Tim Sort — Python/Java’s default; merge-sort-based hybrid
• Master Theorem — the recurrence-solving tool we used in §5.1
• Binary Heap — used in external merge sort’s k-way merge
• Big-O Notation
• Divide and Conquer Paradigm
• SWE Interview Preparation MOC