Given an array of integers, sort it in non-decreasing order using **Merge Sort** — repeatedly split the array in half, sort each half, then merge the two sorted halves back together. This is the classic divide-and-conquer sort: splitting always takes O(log n) levels, and merging two sorted halves takes O(n) work at each level, giving O(n log n) overall — reliably faster than the simple O(n²) sorts on large inputs, and (unlike quicksort) with no bad-input case that degrades it.