Split the array in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front value. The work happens on the way back up: merging two sorted lists is easy.
- Average time
- O(n log n)
- Space
- O(n)
Split the array in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front value. The work happens on the way back up: merging two sorted lists is easy.