A divide-and-conquer algorithm that splits the array into halves, recursively sorts them, then merges the sorted halves.
Time: O(n log n) guaranteed
Space: O(n) auxiliary
Stable: Yes
Colors show recursion depth levels. The auxiliary array is shown below during merges.