Merge sort
Applies to: general, python
Merge sort sorts by splitting the array in half, sorting each half, and merging the two sorted halves. It runs in O(n log n) in every case and is stable, at the cost of O(n) extra space.
[5 2 4 1] -> [5 2] [4 1] -> [2 5] [1 4] -> [1 2 4 5]