Watch Merge Sort Split and Reunite!
Divide: Split array into halves until single elements.
Conquer: Merge sorted halves back together.
Time: O(n log n) always - consistent
performance!
Space: O(n) - Needs auxiliary space for
merging