Merge sort

Imagine two friends each hand you a neatly sorted pile of exam papers, ordered by mark. You want to combine them into one sorted pile. Do you shuffle everything together and start again? No — you glance at the top paper of each pile, take whichever has the smaller mark, and drop it face-down onto your new pile. Repeat. Because each pile is already in order, the smallest paper left is always at the top of one pile or the other, so you never have to look deeper. In a single sweep the two sorted piles become one sorted pile.

That merging trick is the heart of merge sort — one of the fastest and most elegant ways to sort a list. It is built from just two ideas, and this page is really about those two:

Divide and conquer

Merge sort is the classic example of a divide-and-conquer algorithm: a hard problem is broken into smaller copies of the same problem, each solved the same way, and the answers are combined. Sorting a whole list is hard; sorting a list of one item is trivial (it's already sorted!). So the plan is:

  1. Divide — split the list into a left half and a right half.
  2. Conquer — sort each half. How? By merge sort again — this is recursion. The list keeps halving until a piece has 0 or 1 items, which is already sorted and needs no work. That's the base case.
  3. Combine — merge the two now-sorted halves into one sorted list.

The recursion does the splitting; the merge does the real work of putting things in order. Watch one list travel all the way down to single items and back up to sorted:

Read the top half downwards — the list halves until each piece is a lone number (which is trivially "sorted"). Then read the bottom half: neighbouring pieces are merged, pair by pair, until the whole list is back together and in order.

The merge step, up close

Everything depends on merging, so let's do one carefully by hand. We are merging two sorted lists:

\text{left} = [2,\ 5]\qquad\qquad \text{right} = [1,\ 8]

Keep a finger on the front of each list. Compare the two fingers, take the smaller number into the result, and move that finger on one place:

left [2,5] right [1,8] result [] compare 2 vs 1 → take 1 left [2,5] right [8] result [1] compare 2 vs 8 → take 2 left [5] right [8] result [1,2] compare 5 vs 8 → take 5 left [] right [8] result [1,2,5] left is empty → take the rest: 8 left [] right [] result [1,2,5,8] done

Notice the very last line: once one list runs out, the other is already sorted, so we can tip the whole remainder onto the end without any more comparing. Merging two lists of total length n takes at most about n comparisons — one clean pass.

Merge sort in code

This is the whole algorithm: a merge helper that fuses two sorted lists, and a recursive mergeSort that splits, recurses, then merges. Press Run and read the merges it prints — you'll see it merge tiny lists first, then bigger and bigger ones.

function merge(left: number[], right: number[]): number[] { const result: number[] = []; let i = 0, j = 0; // walk both lists, always taking the smaller front item while (i < left.length && j < right.length) { if (left[i] <= right[j]) { result.push(left[i]); i++; } else { result.push(right[j]); j++; } } // one side is empty; the other is already sorted, so tack it on return result.concat(left.slice(i)).concat(right.slice(j)); } function mergeSort(list: number[]): number[] { if (list.length <= 1) return list; // base case: 0 or 1 item is already sorted const mid = Math.floor(list.length / 2); const left = mergeSort(list.slice(0, mid)); // sort the left half... const right = mergeSort(list.slice(mid)); // ...and the right half console.log("merging", left, "+", right); return merge(left, right); // combine the two sorted halves } console.log("sorted:", mergeSort([5, 2, 8, 1, 9, 3, 7, 4]));

The function has recursion's two hallmarks: a base case (a list of length 0 or 1) and a recursive case that calls itself on smaller lists (the two halves). Because each half is strictly shorter, the splitting is guaranteed to stop.

Why so much faster than bubble sort?

Simple sorts like bubble sort and insertion sort take roughly n^2 steps: for each of the n items they may scan much of the list. Merge sort is far cheaper, about n \log_2 n steps. Here's the intuition:

The gap is enormous once lists get big. Sorting a million items: n^2 is a trillion steps, while n \log_2 n is only about twenty million — roughly fifty thousand times less work.

Merge sort was described by John von Neumann in 1945, at the very dawn of the stored-program computer — making it one of the oldest algorithms still in everyday use. It has a lovely practical superpower: because it only ever needs to look at the fronts of two lists at a time, it can sort data far too big to fit in memory. Old machines sorted enormous files by streaming sorted chunks off separate magnetic tapes and merging them — "external" merge sort. The same idea still powers the sorting inside huge databases today.

The merge step feels like magic — one clean pass and two lists become one sorted list — but the magic only works because both halves are already sorted. If you handed merge two unsorted lists, taking the smaller front item would give nonsense, because the smallest number might be buried deep in a pile, not on top.

So don't picture merge sort as "one merge." The recursion's whole job is to guarantee the halves are sorted before you merge them — you sort the smallest pieces first, then merge upward. That's why the base case matters: a single item is sorted for free, giving merge something correct to build on.

One more gotcha: merging cannot happen "in place" like bubble sort's swaps. You need somewhere to put the merged result — the result array in the code above. Merge sort trades a little extra memory (about n spare slots) for its great speed.