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)\) |