Merge sort visualization

Merge sort is a comparison-based sorting algorithm that sorts an array by splitting it in half, sorting each half recursively, and merging the two sorted halves into one. It is a classic divide and conquer algorithm and always runs in O(n log n) time.

How it works

1. If the range has one element (or none), it is already sorted: stop.
2. Split the range in the middle into a left half and a right half.
3. Sort the left half, then sort the right half, using the same steps.
4. Merge the two sorted halves: repeatedly compare the front values of both halves, copy the smaller into the result, and move on. When one half runs out, copy the rest of the other.

A worked example of merge sort

Sort [38, 27, 43, 3, 9, 82, 10]. The recursion first splits the range down to single elements. In order, it splits indexes 0 to 6 into 0 to 3 and 4 to 6; 0 to 3 into 0 to 1 and 2 to 3; 0 to 1 into 0 to 0 and 1 to 1; 2 to 3 into 2 to 2 and 3 to 3; 4 to 6 into 4 to 5 and 6 to 6; 4 to 5 into 4 to 4 and 5 to 5. A single element is sorted already, so the merges then run from the bottom up:

1. Merge indexes 0 to 1 (1 comparison, 2 writes): [27, 38, 43, 3, 9, 82, 10]
2. Merge indexes 2 to 3 (1 comparison, 2 writes): [27, 38, 3, 43, 9, 82, 10]
3. Merge indexes 0 to 3 (3 comparisons, 4 writes): [3, 27, 38, 43, 9, 82, 10]
4. Merge indexes 4 to 5 (1 comparison, 2 writes): [3, 27, 38, 43, 9, 82, 10]
5. Merge indexes 4 to 6 (2 comparisons, 3 writes): [3, 27, 38, 43, 9, 10, 82]
6. Merge indexes 0 to 6 (6 comparisons, 7 writes): [3, 9, 10, 27, 38, 43, 82]

In total: 14 comparisons and 20 writes. The left half (indexes 0 to 3) is completely sorted before the right half is touched, which is the order of the run.

Merge sort pseudocode

Indexes start at 0, as in the code of this lesson. The first call is MERGE-SORT(A, 0, n - 1).

MERGE-SORT(A, lo, hi)
1  if lo >= hi
2      return
3  mid = floor((lo + hi) / 2)
4  MERGE-SORT(A, lo, mid)
5  MERGE-SORT(A, mid + 1, hi)
6  MERGE(A, lo, mid, hi)

MERGE(A, lo, mid, hi)
1  L = copy of A[lo..mid]
2  R = copy of A[mid + 1..hi]
3  i = 0
4  j = 0
5  k = lo
6  while i < length(L) and j < length(R)
7      if L[i] <= R[j]
8          A[k] = L[i]
9          i = i + 1
10     else
11         A[k] = R[j]
12         j = j + 1
13     k = k + 1
14 while i < length(L)
15     A[k] = L[i]
16     i = i + 1
17     k = k + 1
18 while j < length(R)
19     A[k] = R[j]
20     j = j + 1
21     k = k + 1

The <= on line 7 takes the left value on a tie, which makes the sort stable. The two copies on lines 1 and 2 are the O(n) extra space.

Time and space complexity

The array is halved about log n times, so there are about log n levels of splitting. At every level the merges touch each of the n values once. Total work: O(n log n), whatever the input looks like.

Complexity

Best case time	O(n log n)
Average case time	O(n log n)
Worst case time	O(n log n)
Extra space	O(n)

• Time, best, average and worst: O(n log n), because the split depth and the work per level do not depend on the order of the values.
• Space: O(n), because merging copies the halves aside before writing them back. Merge sort is not in place.

Stability

Merge sort is stable: equal values keep their original order. When the two front values are equal, the merge takes the one from the left half, which came first in the original array.

When to use it, and when not to

• Use it when you need a guaranteed O(n log n) time, with no bad inputs.
• Use it when stability matters, for example sorting records by one field after another.
• It fits linked lists and data on disk, where merging reads sequentially.
• Avoid it when memory is tight: the O(n) extra space is its main cost. Quick sort sorts in place, though without a worst-case guarantee.

Where merge sort is used

• Standard library sorts. Python's sorted and list.sort, and Java's sort for objects, use Timsort, a merge sort that first finds runs already in order. JavaScript's Array.prototype.sort has had to be stable since ECMAScript 2019, and V8 implements it with Timsort. Stability is the reason: sorting by one field after another only works if equal records keep their order.
• Data larger than memory. An external sort sorts chunks that fit in memory, writes each chunk to disk as a sorted run, then merges the runs while reading each one sequentially. Databases do this when a sort spills to disk (PostgreSQL reports it as an "external merge" sort), and so does the Unix sort command.
• Linked lists. Merging needs only sequential access and no index, so merge sort suits lists. The Linux kernel's list_sort, which sorts its linked lists, is a merge sort.

Related algorithms and variations

A bottom-up version has no recursion: it merges runs of 1 element into runs of 2, then 4, then 8, until one run is left. A natural merge sort starts from the runs already in the data, which is how Timsort reaches O(n) on input that is already sorted. When many sorted runs must be combined, a k-way merge keeps the front value of each run in a heap. Each time the merge takes a value from the right half, adding the number of values still waiting in the left half counts the inversions of the array as a by-product.

For the other O(n log n) sorts, see quick sort (merge sort vs quick sort) and heap sort (merge sort vs heap sort). For small inputs, insertion sort can win (insertion sort vs merge sort).