Mergesort is a divide-and-conquer comparison sort that recursively splits the array in half, sorts each half, then merges them. It guarantees O(n log n) on every input, and is the basis for Java's Arrays.sort on objects.
| Best | Average | Worst | Space (Worst) |
|---|---|---|---|
Ω(n log n) |
Θ(n log n) |
O(n log n) |
O(n) |
Split the array at the midpoint. Recursively sort each half. Merge the two sorted halves into one by walking both with two pointers, repeatedly taking the smaller head. The merge step is the workhorse — every element is compared and copied O(log n) times, giving the n log n total.
def mergesort(arr):
"""Top-down recursive mergesort."""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = mergesort(arr[:mid])
right = mergesort(arr[mid:])
return _merge(left, right)
def _merge(left, right):
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
out.extend(left[i:])
out.extend(right[j:])
return out
print(mergesort([3, 6, 1, 8, 2, 9, 4])) # [1, 2, 3, 4, 6, 8, 9]