Mergesort
Stable sorting.
Stable Sorting
Mergesort is a divide-and-conquer sort that splits the array in half, sorts each half, then merges them back together. It is O(n log n) in every case and stable.
The Divide Step
Recursively split the array at the midpoint until each piece has one element. A single element is trivially sorted, which is the base case.