Sorting Simple sorts
145. Insertion Sort
You are given an array of integers nums. Sort it in ascending order, smallest first, using insertion sort.
Insertion sort keeps a sorted part at the front of the array. At the start, the sorted part is just the first element. Each step takes the next element and moves it left, past every larger value in the sorted part. The sorted part then holds one more element.
Change nums itself. The function returns nothing; the answer is what nums holds after it finishes. Every
copy of a repeated value stays.
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 = [4, 7, 2, 7, -5]
[-5,2,4,7,7]Explanation: The 7 is larger than the 4, so it stays. The 2 moves left past the 7 and the 4. The second 7 stops next to the first one, and −5 moves all the way to the front.
Example 2
Input: nums = [-1, 0, 0, 3, -2]
[-2,-1,0,0,3]Explanation: The first four values are already in order, so nothing moves until the last step. Then −2 moves past all four of them.
Example 3
Input: nums = [10, 5, 0, -5]
[-5,0,5,10]Explanation: The array is in reverse order, so every value moves all the way to the front.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 2000-109 ≤ nums[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.