Given an array of integers nums, sort the array in ascending order using the Merge Sort algorithm — recursively split the array in half until each piece is a single element (trivially sorted), then merge sorted pairs back together in linear time.
nums = [8,4,3,7,6][3,4,6,7,8]Merging two already-sorted sequences takes only O(n) — a single linear scan that compares the fronts of each side and copies the smaller one across. There are O(log n) levels of splitting (each level halves the range), so total work is O(n log n) — in the best, average, and worst case alike, unlike Quick Sort's adversarial O(n²). Merge Sort is also stable (the left[i] <= right[j] tie-break keeps equal elements in their original relative order) but not in-place — every merge needs an auxiliary buffer to hold a snapshot of both halves before overwriting them, which is the classic time/space tradeoff versus Quick Sort's O(log n) average auxiliary space.