Sorting Algorithm

Merge Sort

“The Reliable Bureaucrat”

Time: O(n log n)

Space: O(n)

History

Invented by the legendary John von Neumann in 1945. It was one of the first algorithms designed for the EDVAC, one of the earliest computers.

Merge Sort is the "slow and steady" alternative to Quick Sort. It doesn't rely on luck or pivots. It guarantees performance with a mathematical ruthlessness. It is the engine behind Python's sort and Java's object sort.

How It Works

Merge Sort is the ultimate "Divide and Conquer" algorithm. It splits the list in half until it has lists of size 1, then merges them back together in sorted order.

The Algorithm Step-by-Step

Divide: Cut the array in half.
Recurse: Do it again until you have arrays with 1 element.
Conquer (Merge): Take two sorted sub-arrays and zipper them together into one larger sorted array.
Repeat: Until the whole array is reconstructed.

Why It Works

Merging two sorted lists is easy ( $O(n)$ ). You just look at the head of both lists and pick the smaller one.

Best CaseO(n log n)

It splits and merges regardless of the data. It does the full work every time.

Worst CaseO(n log n)

This is its superpower. It never degrades to quadratic time. It is consistent.

Average CaseO(n log n)

Predictable, stable, and reliable.

SpaceO(n)

The trade-off. It needs a temporary array to hold the merged items. It burns memory to buy stability and consistency.

Code Walkthrough

Real implementations in multiple programming languages. Select a language to view idiomatic code.

1def merge_sort(arr: list[int]) -> list[int]:
2    """Sort array using merge sort. Returns new sorted array."""
3    if len(arr) <= 1:
4        return arr
5
6    mid = len(arr) // 2
7    left = merge_sort(arr[:mid])
8    right = merge_sort(arr[mid:])
9
10    return merge(left, right)
11
12def merge(left: list[int], right: list[int]) -> list[int]:
13    """Merge two sorted arrays into one sorted array."""
14    result = []
15    i = j = 0
16
17    while i < len(left) and j < len(right):
18        if left[i] <= right[j]:
19            result.append(left[i])
20            i += 1
21        else:
22            result.append(right[j])
23            j += 1
24
25    result.extend(left[i:])
26    result.extend(right[j:])
27    return result