Mergesort: time and space complexity

High interview relevanceRoadmap: Intermediate

Time	Θ(n log n) in every case
Space	O(n)

Why it costs this much

Halving the input gives log n levels, and merging at each level touches every item once.

Code

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])   # log n levels
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):                  # O(n) per level
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

Python is the baseline example used across the site.

Common pitfalls

Arrays need O(n) extra space. Take from the left run on ties, or the sort stops being stable.

Operation by operation

Operation	Best	Average	Worst	Space
Merge sort	O(n log n)	O(n log n)	O(n log n)	O(n)

Merge sort. Array version with a merge buffer. Stable. A linked-list version needs only O(log n) stack space.