Merge sort recursively breaks a list into smaller and smaller sublists. When single elements are reached, these are then recursively recombined as ordered sublists.
MERGESORT(A):
n ← size of A
IF n = 1 THEN RETURN A
left ← MERGESORT( A[1 to ⌈n/2⌉] )
right ← MERGESORT( A[⌈n/2⌉+1 to n] )
RETURN merge(left, right)| Worst | Average | Best | |
|---|---|---|---|
| Time | \(O(n \log n)\) | \(\Theta(n \log n)\) | \(\Omega(n \log n)\) |
| Space | \(O(n)\) |