Sorting Divide-and-conquer sorts
150. Sort an Array
You are given an array of integers nums. Return the same numbers in ascending order, smallest first.
Write the sorting yourself. Do not call your language's built-in sort or any library function that sorts
for you, such as std::sort, Arrays.sort, sorted or Array.prototype.sort.
Every copy of a repeated value stays in the answer, so the answer has exactly as many elements as nums.
Example 1
Input: nums = [9, -4, 0, 9, 3, -11]
[-11,-4,0,3,9,9]Explanation: The smallest value, −11, comes first and the two 9s come last. Both 9s stay, so the answer has six
elements, like nums.
Example 2
Input: nums = [3, 3, 1, 3]
[1,3,3,3]Explanation: The 1 moves to the front and the three 3s follow it.
Example 3
Input: nums = [2147483647, -2147483648, -1, 1]
[-2147483648,-1,1,2147483647]Explanation: The values can be as small as −231 and as large as 231 − 1, the two ends of a 32-bit integer.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-231 ≤ nums[i] ≤ 231 − 1
Clarifying questions
What you would ask an interviewer before writing any code.