Sorting Simple sorts
147. Insertion Sort with Recursion
You are given an array of integers nums. Sort it in ascending order, smallest first, using insertion sort
written with recursion.
The recursion works like this. To sort the first n elements, first sort the first n − 1 of them with a recursive call. Then insert the last of the n elements into that sorted part, at the place where it belongs. A single element is already sorted, so the recursion stops there.
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, with a recursive call in place of the outer loop. 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 = [5, -1, 8, 2, -1]
[-1,-1,2,5,8]Explanation: The recursive calls sort the first four elements into [-1, 2, 5, 8]. Then the last −1 is inserted. It
moves left past 8, 5 and 2, and stops just after the other −1.
Example 2
Input: nums = [0, -7, 1000000000, -1000000000]
[-1000000000,-7,0,1000000000]Explanation: The last element, −109, is the smallest of all. The final insert moves it past every other element to the front.
Example 3
Input: nums = [42]
[42]Explanation: One element is already sorted, so the recursion stops at once and nothing moves.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 1000-109 ≤ nums[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.