Sorting Divide-and-conquer sorts
148. Merge Sort
You are given an array of integers nums. Sort it in ascending order, smallest first, using merge sort.
Merge sort splits the array into two halves, sorts each half the same way, and then merges the two sorted halves into one sorted array. A part with a single element is already sorted.
Change nums itself. The function returns nothing; the answer is what nums holds after it finishes. Every
copy of a repeated value stays, so equal values end up next to each other.
Write the sort yourself. Do not call your language's built-in sort, such as std::sort, Arrays.sort,
list.sort or Array.prototype.sort.
Example 1
Input: nums = [38, -7, 15, 0, -7, 22, 4]
[-7,-7,0,4,15,22,38]Explanation: The halves [38, -7, 15, 0] and [-7, 22, 4] are sorted to [-7, 0, 15, 38] and [-7, 4, 22]. Merging
those two gives the answer, with both −7s at the front.
Example 2
Input: nums = [0, -1000000000, 1000000000, 0]
[-1000000000,0,0,1000000000]Explanation: The values can be as low as −109 and as high as 109. The two 0s stay side by side in the middle.
Example 3
Input: nums = [8, 6, 4, 2, 1]
[1,2,4,6,8]Explanation: The array starts in reverse order, largest first, and comes back smallest first.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.