Slide it into place
Push bigger values one step right until the new one fits. About 9 minutes.
Slide bigger values one step right
This is how most people sort a hand of playing cards. The cards in your hand are already in order, and you pick up a new one. Look at the card just before its spot: if it is bigger, slide it one step right to make room, then look at the next card, and so on. Stop at a card that isn't bigger, because the new card goes right after it.
shifts = 0
j = i - 1
while j >= 0 and nums[j] > nums[i]:
shifts += 1
j -= 1
return shiftsThe card 8 is bigger than 2, so it shifts right. Shift 1.
Shifts count the bigger values before it
Each shift moves exactly one value that is bigger than the new one out of the way. So the total number of shifts is exactly the number of earlier values that are bigger than the new one.
A card that is already the smallest so far, or a repeat of one you hold, needs no shifts at all, while one smaller than everything in your hand slides all the way to the front.
nums = [1, 4, 7, 10, 5], and nums[0..3] is already sorted. Inserting nums[4] = 5, how many shifts does it take?
- A2
- B3
- C1
Show the answer
2. 10 and 7 are both bigger than 5, so they each shift once. 4 isn't bigger than 5, so shifting stops there.
Shifts to insert
nums[0..i − 1] is already sorted from smallest to largest (this is always true partway through insertion sort). Inserting nums[i] shifts every value right of it that's bigger, one place right, and stops at the first value that isn't bigger than nums[i]. Return how many shifts that takes.
nums = [1, 3, 5, 8, 2], i = 4 → 3
1 ≤ n ≤ 200,000 · 0 ≤ i < n · nums[0..i-1] is sorted from smallest to largest · −1,000,000,000 ≤ each value ≤ 1,000,000,000