Merge Sort

Merge sort sorts an array in two moves: split it into runs of one value, then merge the runs back together in order. A run is a stretch of cells in sorted order, so a run of one value comes for free. The merge is where the work happens, and the figure above shows both moves.

Split down, merge up

The plan is recursive. Cut the live range in half, sort the left half, sort the right half, and merge the two. Each half gets the same treatment until every run holds a single value. That is the base case, and it costs nothing.

In the figure, a dashed divider shows each cut, and the bracket above the cells shows the live range [lo, hi): the indices from lo up to, but not including, hi. A cell gains an accent outline once its run settles into order.

How one merge works

A merge walks two sorted runs with a head on each. The heads are the L and R markers in the figure. Compare the values under the heads, copy the smaller one into the buffer, and move that head one cell right.

1. Compare the values under L and R.

2. Copy the smaller value into the next buffer slot, then move that head one cell right.

3. When one run empties, copy the rest of the other run across. It is already in order.

A tie goes to the left head. That one choice keeps the sort stable: equal values never swap their original order. You can sort by one key and then by another without losing the first ordering.

The buffer is the extra row that appears under the array during a merge. When both runs are copied across, the buffer writes back over the original cells, and the whole range becomes one ordered run.

def merge_sort(a):
	if len(a) <= 1:
		return a
	mid = len(a) // 2
	left = merge_sort(a[:mid])
	right = merge_sort(a[mid:])
	return merge(left, right)

def merge(left, right):
	out = []
	i = j = 0
	while i < len(left) and j < len(right):
		if left[i] <= right[j]:
			out.append(left[i])
			i += 1
		else:
			out.append(right[j])
			j += 1
	return out + left[i:] + right[j:]

The whole sort on four values

Take the figure's starting array, [38, 27, 43, 3]. The splits come first: [0, 4) becomes [0, 2) and [2, 4), then four runs of one cell each. What follows is three merges.

1. Merge [0, 1) with [1, 2). The heads compare 38 with 27. The right head wins, 27 enters the buffer first, and 38 copies across after it. The range [0, 2) now reads [27, 38].

2. Merge [2, 3) with [3, 4) the same way. The range reads [3, 43].

3. Merge [0, 2) with [2, 4). The heads compare 27 with 3, then 27 with 43, then 38 with 43. The buffer fills as [3, 27, 38], and 43 copies across last. Sorted.

Three merges for four values: n - 1 merges for n single-cell runs, with five comparisons here. Edit the array (up to eight values) and press play to watch your own.

Why the work adds up to O(n log n)

Splitting halves the range each time, so the split depth is log2 n. The merges at one depth touch every cell once, because those merges partition the array. n cells per depth times log2 n depths gives O(n log n).

The four-value sort has three depths:

This bound is a guarantee, not an average. Quicksort runs faster on many inputs, but its worst case is O(n^2), and a bad pivot can trigger it. Merge sort has no bad input. When a deadline matters more than constants, that predictability is worth the extra memory.

What it costs in space

Array merge sort is not in place. The buffer needs O(n) extra cells, and the figure keeps that cost visible: the buffer is exactly as long as the range being merged. Linked lists escape the charge, because merging relinks nodes instead of copying values. That is why merge sort is the standard sort for linked data.

When merge sort is the right sort

Reach for merge sort when one of these holds:

• You need a guaranteed O(n log n). No input can make the sort degenerate.

• You need a stable sort. Equal keys keep their original order, so multi-key sorts compose.

• The data is a linked list, or a stream too big for memory. Merging needs sequential access only, so external sorts on disk are merge sorts.

In-memory standard libraries often prefer quicksort hybrids for the constants. Even there, merge sort shows up: Python and Java sort objects with Timsort, a merge sort tuned to exploit runs that are already sorted.

The practice problems below lean on both moves. Sort List is the linked-list sort from the space section, and the counting problems ask each merge to total how many right-run values jump ahead of a left-run value.