Merge sort is a divide-and-conquer, stable sort that runs in guaranteed O(n log n) time. It splits the array in half, sorts each half recursively, then merges the two sorted halves.
The idea
A single element is already sorted (base case). Merging two sorted lists is linear, and we do log n levels of merging.
Example
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
return merge(left, right)
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps it stable
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:]); result.extend(b[j:])
return result
merge_sort([5, 2, 4, 1, 3]) # -> [1, 2, 3, 4, 5]
Complexity
- Time: O(n log n) in all cases (best, average, worst).
- Space: O(n) for the merge buffers (not in-place).
When to use / pitfalls
Ideal when you need stability or guaranteed O(n log n), and for linked lists and external sorting of huge files. The extra O(n) memory is its main drawback.
Why it matters
Merge sort guarantees O(n log n) regardless of input, unlike quicksort's O(n²) worst case.
Its stability preserves the relative order of equal keys, which matters for multi-key sorting.
The merge step is a reusable primitive, and the divide-and-conquer structure is a template you will reuse everywhere.