programmingconcepts

§ 3.5 · Algorithms

Merge sort

Split the list in half, sort each half, then merge the two sorted halves into one.

Merge sort splits a list in half, sorts each half recursively, then merges the two sorted halves by repeatedly taking the smaller front value. It always takes O(n log n) time, whatever the input order, and it is stable: equal values keep their original order. The cost is O(n) extra memory for merging.

Time
O(n log n) in every case
Extra space
O(n)
Stable
Yes
In place
No
Requires
RecursionBig O
def merge_sort(a, lo, hi):
    if lo >= hi:
        return
    mid = (lo + hi) // 2
    merge_sort(a, lo, mid)
    merge_sort(a, mid + 1, hi)
    left, right = a[lo:mid + 1], a[mid + 1:hi + 1]
    i = j = 0
    for k in range(lo, hi + 1):
        if j == len(right) or (i < len(left) and left[i] <= right[j]):
            value, i = left[i], i + 1
        else:
            value, j = right[j], j + 1
        a[k] = value

Press Play or Step to start.

0 comparisons0 swapsstep 0 / 00 / 16 in placecomparingmovingpivot

Fig. 3.5. Each orange bar is a value being copied back from the merge buffer. Blue marks the two positions being compared while both halves still have values.

Intuition

Two people each hold a sorted stack of numbered cards. To combine them, keep comparing the top cards and take the smaller one. You never have to look further down either stack, so merging is fast.

Merge sort turns any list into that easy case: split it until every piece has one value (a list of one is sorted), then merge pieces back together, two at a time.

How it works

  1. If the range has one value or none, it’s sorted. Stop.
  2. Split the range at the middle and merge sort each half.
  3. Copy the two sorted halves aside.
  4. Repeatedly compare the front of each half and write the smaller value back into the array.
  5. When one half runs out, copy the rest of the other half.

Complexity

Each level of splitting merges n values in total, and halving n until pieces have one value takes about log₂ n levels. So merge sort makes about n log₂ n writes, whatever the input order. It never has a bad case, which is its big advantage over quicksort.

The cost is memory: merging needs a buffer as large as the range being merged, O(n) extra space.

Common mistakes

  1. Using < instead of <= when merging. Taking from the right half on ties breaks stability.
  2. Forgetting the leftovers. When one half is empty, the rest of the other half still has to be copied.
  3. Allocating a new buffer for every merge. It works, but one buffer reused across merges is much faster.
  4. Splitting at the wrong place. With mid = (lo + hi) / 2, the halves are lo..mid and mid + 1..hi. Using mid in both repeats a value; skipping it loses one.

When to use it

When you need a stable sort or a guaranteed O(n log n) worst case, for linked lists (merging needs no random access), and for data too big for memory (external merge sort reads sorted chunks from disk).

Check yourself

Check yourself

Merging [1, 4, 9] with [2, 3, 10]: what is the 4th value written?

Check yourself

How many levels of splitting does merge sort need for 16 values?

Sources

  • John von Neumann described merge sort in 1945; see Knuth, The Art of Computer Programming, Vol. 3, section 5.2.4.
  • Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 2.3, “Designing algorithms.”

Newsletter

One new concept each week, by email.

Signup opens soon.