Merge Sort

Merge sort splits the array in half, sorts each recursively, and merges the two sorted halves, guaranteeing O(n log n) and stability.

Divide, sort, merge

Merge sort is the canonical divide-and-conquer sort. It splits the array into two halves, recursively sorts each, and then merges the two sorted halves into one sorted whole. The merge walks both halves with two pointers, always taking the smaller front element, so it runs in linear time.

Why the cost is O(n log n)

The recursion halves the problem at each level, so there are about log n levels. Each level does O(n) total work across all the merges. Multiplying gives O(n log n), and this holds in the best, average, and worst cases alike because the split is always even and the merge always linear.

• Time: O(n log n) in all cases
• Extra space: O(n) for the merge buffer
• Stable: yes
• Well suited to linked lists and external sorting

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    L, R = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            out.append(L[i]); i += 1
        else:
            out.append(R[j]); j += 1
    out.extend(L[i:]); out.extend(R[j:])
    return out

Merging linked lists

Merge sort is the sort of choice for linked lists, because merging two sorted lists needs only pointer rewiring and no auxiliary array, dropping the space overhead to O(1). Splitting a list is done with a slow-and-fast pointer walk to find the midpoint. This makes merge sort strictly better than quicksort for lists, where random access is expensive.

Strengths and the space cost

Merge sort's guaranteed O(n log n) and its stability make it the default when worst-case bounds or stable ordering matter. It also shines for data too large for memory: external merge sort streams sorted runs from disk and merges them, which is how large database sorts work. Its main drawback for arrays is the O(n) auxiliary buffer, which quicksort avoids by sorting in place.