Merge Sort

Updated September 30, 20263 min read

In short

Merge sort is a divide and conquer sorting algorithm that splits a list in half, sorts each half recursively, and merges the sorted halves in O(n log n) time.

What is merge sort?

Merge sort is a sorting algorithm that repeatedly splits a list in half until every piece holds a single item, which is sorted by definition, and then merges those pieces back together in order. It was invented by John von Neumann in 1945 and is a textbook example of divide and conquer. Its running time is O(n log n) in the best, average, and worst case, so its performance never degrades on unlucky input.

All the real work happens in the merge step. Given two sorted lists, you compare their first items, move the smaller one to the output, and repeat until both lists are empty, which takes O(n) time. The list is halved about log2(n) times, and each level of halving requires merging n items in total, which gives O(n log n) overall. The usual array version needs O(n) extra memory for the merged output, and because it takes from the left half when two items are equal, merge sort is stable, keeping equal items in their original order.

Imagine two piles of exam papers, each already sorted by student name: to combine them, you keep taking whichever top sheet comes first alphabetically. Merge sort is used where predictable performance or stability matters, and it is the basis of Timsort, the hybrid algorithm behind Python's sorted() and Java's sorting of objects. Because merging reads data sequentially, merge sort also powers external sorting, where data too large for memory is sorted in chunks on disk and the chunks are then merged, which is how databases handle large ORDER BY queries. It suits linked lists well too, since merging only relinks nodes and needs no extra array.

Merge sort is most often compared with quicksort. Merge sort guarantees O(n log n) and is stable, but it needs O(n) extra memory for arrays; quicksort sorts in place and is usually faster in practice thanks to better use of the CPU cache, but it can degrade to O(n^2) and is not stable. A handy way to remember the difference: merge sort does its work when combining, while quicksort does its work when dividing.

Key takeaways

Merge sort splits a list in half, sorts each half recursively, and merges the results.
It runs in O(n log n) time in the best, average, and worst case.
The array version needs O(n) extra memory.
It is stable: equal items keep their original order.
It underlies Timsort and the external sorting of data too large for memory.

Example

Merge sort in Pythonpython

def merge_sort(items):
    if len(items) <= 1:
        return items  # base case: 0 or 1 items are already sorted
    mid = len(items) // 2
    left, right = merge_sort(items[:mid]), merge_sort(items[mid:])  # divide
    merged, i, j = [], 0, 0
    while i < len(left) and j < len(right):  # merge: O(n) per level
        if left[i] <= right[j]:  # <= keeps equal items in order (stable)
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    return merged + left[i:] + right[j:]  # append whatever is left over
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))  # [3, 9, 10, 27, 38, 43, 82]

Readers ask

What is the time complexity of merge sort?

Merge sort runs in O(n log n) time in the best, average, and worst case, because the list is halved about log n times and each level merges n items. It needs O(n) extra space when sorting arrays.

Is merge sort better than quicksort?

It depends. Merge sort guarantees O(n log n) and is stable, which suits linked lists, external sorting, and cases where equal items must keep their order. Quicksort sorts in place with less memory and is usually faster on arrays in practice.

Is merge sort stable?

Yes, as long as the merge step takes from the left half when two items are equal. That is why merge-based algorithms such as Timsort are used when a stable sort is required.

Often compared

Merge Sort vs QuicksortMerge sort guarantees O(n log n) time but uses extra memory, while quicksort partitions around a pivot in place and is usually faster, but can slow to O(n²).