Merge sort explained: how it works, code and complexity

The idea in plain words

A list with zero or one element is already sorted. For a longer list:

1. Divide: split the list into a left half and a right half.
2. Conquer: sort each half with merge sort.
3. Combine: merge the two sorted halves. Compare the first element of each, move the smaller one to the output, and repeat until one half is empty; then copy what is left of the other.

All the real work happens in the merge step, and merging two sorted lists of total length n takes only n − 1 comparisons at most.

Worked example, step by step

Sort [38, 27, 43, 3, 9, 82, 10].

The final merge compares fronts: 27 vs 3 takes 3, 27 vs 9 takes 9, 27 vs 10 takes 10, 27 vs 82 takes 27, 38 vs 82 takes 38, 43 vs 82 takes 43, then 82 is copied. Six comparisons for seven elements.

Python implementation

def merge(left, right):
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:     # <= takes from left on ties: stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:])            # one of these is empty
    out.extend(right[j:])
    return out
def merge_sort(items):
    """Return a new sorted list."""
    if len(items) <= 1:
        return list(items)
    mid = len(items) // 2
    return merge(merge_sort(items[:mid]), merge_sort(items[mid:]))
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))   # [3, 9, 10, 27, 38, 43, 82]
print(merge_sort([]))                           # []

This top-down version is clear but copies slices. A bottom-up version avoids recursion entirely: merge runs of width 1, then 2, then 4, and so on.

def merge_sort_bottom_up(items):
    a = list(items)
    width = 1
    while width < len(a):
        for lo in range(0, len(a), 2 * width):
            mid, hi = lo + width, lo + 2 * width
            a[lo:hi] = merge(a[lo:mid], a[mid:hi])
        width *= 2
    return a

The bottom-up version reuses merge from above. The standard library also has heapq.merge, which lazily merges any number of sorted iterables.

Time and space complexity

The recurrence is T(n) = 2T(n/2) + O(n). Each level of the recursion tree does O(n) work in total and there are about log₂ n levels, so the total is O(n log n). For a million items that is about 20 levels.

How merge sort compares with other sorts

Merge sort is stable because the merge takes from the left half when two elements are equal, so equal elements keep their order. Compared with quicksort, it has a guaranteed O(n log n) worst case but needs O(n) extra memory and usually more data movement on arrays. Compared with heapsort, it is stable and accesses memory sequentially, which is friendly to caches and disks.

Variants and common mistakes

• Natural merge sort detects runs that are already sorted and merges them, giving O(n) on sorted input. Timsort is a refined natural merge sort that uses binary insertion sort for short runs.
• Switch to insertion sort for small sublists (for example, fewer than about 10 to 30 elements) to cut overhead.
• On linked lists, merge sort needs no extra buffer: merging only relinks nodes, so it is the usual choice for sorting a linked list.
• External merge sort sorts chunks that fit in memory, writes them to disk, then performs a k-way merge. Databases and tools such as GNU sort use this idea for large files.
• Counting inversions: during the merge, each time an element is taken from the right half, it is smaller than all remaining elements of the left half.

When to use merge sort

Choose merge sort when you need a stable sort with a guaranteed O(n log n) time, when sorting linked lists, or when data is too large for memory. In Python, simply call sorted() or list.sort(): they implement Timsort, which is a merge sort variant, so you already get these properties. Writing merge sort by hand is a classic interview task, often extended to counting inversions or merging k sorted lists.