Merge sort is a classic divide-and-conquer algorithm. It repeatedly splits the array into halves until each part contains a single element, then merges those parts back together in sorted order.

Its time complexity is a consistent O(n log n) regardless of the input. Merge sort is also stable and widely used in practice, particularly for linked lists and large datasets that do not fit entirely in memory.

This chapter covers how merge sort works, how to implement it, and why it remains a foundational sorting algorithm.

Merge sort is a divide-and-conquer algorithm. It breaks a problem into smaller subproblems, solves each one independently, and then combines the results. For sorting, that means three steps:

The recursion bottoms out when a subarray has zero or one element, since a single element is already sorted. The merge step then combines two sorted subarrays into one.

Here is what the full split-and-merge process looks like for a small array:

The top half of the diagram shows the divide phase, where we keep splitting until every subarray has one element. The bottom half shows the combine phase, where sorted subarrays merge back together, growing larger at each level until the full array is sorted.

Why O(n log n) in All Cases?

Unlike quicksort, which can degrade to O(n^2) on bad inputs, merge sort always splits the array in half (within one element for odd sizes). That means:

The input order does not change this. Merge sort does the same amount of work on sorted, reversed, or random input because the splitting and merging structure is fixed.

The algorithm has two core pieces: the recursive splitting logic and the merge procedure.

The Recursive Structure

The high-level logic has five steps:

By the time merge() is called, both halves are already sorted: arr[left..mid] on the left, arr[mid+1..right] on the right. The merge step's only job is to combine them into one sorted range.

The Merge Procedure

Merging two sorted arrays uses a two-pointer technique:

This merge step is what gives merge sort its name, and it runs in O(n) time because each element is visited exactly once.

At each step of the merge, the algorithm compares the front elements of both halves and picks the smaller one. Because both halves are sorted, the merged result is also sorted.

The implementation uses <= (not <) when comparing elements from the left and right halves. This is what makes merge sort stable: equal elements from the left half always come before equal elements from the right half, which preserves their original relative order.

Trace merge sort on the array [38, 27, 43, 3, 9, 82, 10], following the recursion through both splits and merges. The code uses mid = left + (right - left) / 2 with right inclusive, so a range of size 7 splits into 4 + 3 elements.

Phase 1: Divide

The algorithm splits the array recursively until every subarray has at most one element.

At Level 3, every subarray is a single element. Single elements are sorted by definition, so the recursion starts unwinding. The [10] subarray at Level 2 is already a single element and waits at this level until its sibling [9, 82] finishes.

Phase 2: Merge (Bottom-Up)

Merging proceeds upward, combining sorted subarrays at each level.

Merge [38] and [27]:

Merge [43] and [3]:

Merge [27, 38] and [3, 43]:

Merge [9] and [82]:

Merge [9, 82] and [10]:

Final Merge [3, 27, 38, 43] and [9, 10, 82]:

Both halves have multiple elements here, so the pointers alternate between sides several times before either half is exhausted.

The final sorted array is [3, 9, 10, 27, 38, 43, 82].

The merge step never goes back or re-examines elements. Each element is compared and placed exactly once per merge, which is why each merge level takes O(n) total work.

Why O(n) Space?

Each merge step creates temporary arrays to hold the two halves being merged. At the top level, the temporary arrays hold all n elements. While deeper recursion levels use smaller arrays, those arrays are freed before the top-level merge begins (since recursion unwinds bottom-up). So the peak additional memory usage is O(n).

The call stack also uses O(log n) space due to the recursion depth, but this is dominated by the O(n) temporary arrays.

Stability

Merge sort is stable. The merge step uses <= (not <) when comparing the front elements of the two halves, so an element from the left half is taken first whenever it equals an element on the right. Since the left half originally appeared earlier in the input, equal elements preserve their original order.

This makes merge sort a common choice when sorting records by multiple fields: a stable sort on the secondary key followed by a stable sort on the primary key produces a result correctly ordered by primary, with ties broken by secondary.

Comparison with Other O(n log n) Sorts

Merge sort trades extra memory for guaranteed performance and stability. Quick sort is typically faster due to better cache locality, but it cannot guarantee O(n log n) without careful pivot selection.

Good For

Not Ideal For