Merge sort

Prerequisites

• Recursion: a function that calls itself on a smaller input.
• Logarithms: $\log_2 n$ is how many times you can halve $n$ before reaching 1.
• Big-O notation (see Complexity analysis).

The analogy

How it works

Start with one merge by hand

Splitting [4, 1, 3, 2] gives [4] [1] [3] [2]. Merging pairs gives [1, 4] and [2, 3]. Now merge those two. Guess first, then open "Check".

Finish the picture

Now zoom out to the whole run on [4, 1, 3, 2].

• Splitting. Predict: how many levels of halving until every piece has one number?
  Check

  2 levels: 4 → 2 + 2 → 1 + 1 + 1 + 1. That's $\log_2 4 = 2$.

• Merging. Predict: how many comparisons in total across all merges?
  Check

  1 for [1, 4], 1 for [2, 3] and 3 for the final merge: 5 comparisons.

The rule in plain words

If the piece has one number, it's sorted: stop. Otherwise cut it in half and sort each half the same way.

Then merge: compare the two fronts, move the smaller one to the output, and repeat. When one half runs out, copy the rest of the other.

The code

Read this code after you have done one merge by hand. It will make more sense.

/* Merge sorted a[lo..mid) and a[mid..hi) through tmp. */
void merge(int a[], int tmp[], int lo, int mid, int hi) {
    int i = lo, j = mid, k = lo;
    while (i < mid && j < hi)
        tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];   /* <= keeps it stable */
    while (i < mid) tmp[k++] = a[i++];                 /* copy leftovers */
    while (j < hi)  tmp[k++] = a[j++];
    for (k = lo; k < hi; k++) a[k] = tmp[k];
}

void merge_sort(int a[], int tmp[], int lo, int hi) {   /* sorts a[lo..hi) */
    if (hi - lo < 2) return;                           /* one item: sorted */
    int mid = lo + (hi - lo) / 2;
    merge_sort(a, tmp, lo, mid);
    merge_sort(a, tmp, mid, hi);
    merge(a, tmp, lo, mid, hi);
}

graph TD
  A["4 1 3 2"] -->|split| B["4 1"]
  A -->|split| C["3 2"]
  B --> D["4"]
  B --> E["1"]
  C --> F["3"]
  C --> G["2"]
  D & E -->|merge| H["1 4"]
  F & G -->|merge| I["2 3"]
  H & I -->|merge| J["1 2 3 4"]
          

How fast is it?

Halving gives $\log_2 n$ levels, and each level moves all $n$ numbers once. Multiply the two:

Nothing here depends on the order of the input, so the best, average and worst cases are all the same.

Common mistakes

• Forgetting to copy the leftovers after one half runs out, which silently loses numbers.
• Using < instead of <= in the merge, which breaks stability.
• Mixing up range ends: this code uses half-open ranges [lo, hi), so the base case is hi - lo < 2.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• The merge works because both halves are sorted, so the smaller front is always the smallest number left.
• It is $O(n \log n)$ in every case because there are $\log_2 n$ levels and each moves all $n$ numbers.
• It needs $O(n)$ extra space because the merge writes into a scratch array.
• It is stable because ties are taken from the left half first.
• It suits linked lists and huge files because merging only reads each sequence front to back.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is merging like combining two sorted piles of exams?
   Sample answer

   You look at the top sheet of each pile and always take the one that comes first. You never need to look deeper, because each pile is already in order.

2. Walk through merge sort on [4, 1, 3, 2].
   Sample answer

   Split to [4] [1] [3] [2], merge pairs into [1, 4] and [2, 3], then merge those: take 1, 2, 3, and copy 4, giving [1, 2, 3, 4].

3. Why does the merge use <= instead of <?

   A good answer mentions which half wins a tie.

   Sample answer

   On a tie it takes the element from the left half, which came first in the input. That keeps equal items in their original order, so the sort is stable.

4. So what is merge sort, in one sentence?
   Sample answer

   It splits the array in half, sorts each half recursively, and merges the two sorted halves.

5. Why is merge sort $O(n \log n)$?

   A good answer counts the levels and the work per level.

   Sample answer

   Halving gives $\log_2 n$ levels, and each level's merges together move all $n$ numbers once. So the total is $n \log n$.

6. What are its best, average and worst cases, and its extra space?
   Sample answer

   $O(n \log n)$ in all three cases, because the work doesn't depend on the input order. Extra space is $O(n)$ for the scratch array.

7. Why is it not in-place, and when does that not matter?
   Sample answer

   The merge writes into a separate array of size $n$. On linked lists, you can merge by relinking nodes, so no extra array is needed.

8. When would you pick merge sort over quick sort?
   Sample answer

   When you need stability or a guaranteed $O(n \log n)$ worst case, or when sorting linked lists or files too big for memory. Quick sort is usually faster on plain arrays in RAM.

9. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the half-open ranges and the exact copy count. I'd keep "split until size one, then merge by taking the smaller front", the split/merge picture, and "$O(n \log n)$ always, stable, needs $O(n)$ memory".

External resources

• VisuAlgo: Sorting: pick "MER" and watch the split and merge phases.
• GeeksforGeeks: Merge sort: an article with code and a recursion-tree picture.
• Wikipedia: Merge sort: variants, including bottom-up and external merge sort.
• MIT OCW 6.006 Introduction to Algorithms: university lectures that cover merge sort.

Videos

• YouTube: merge sort as a folk dance: the AlgoRythmics video for merge sort.
• YouTube search: merge sort explained: pick a short walkthrough.