Insertion Sort Shift Count
Problem
Insertion sort places each new value by sliding every larger value in the sorted part one slot to the right. Given a list of numbers, return how many single-slot slides insertion sort performs while sorting it into ascending order. Equal values never slide past each other, and the input list must not be modified.
Examples
Input: nums = [3, 1, 2]
Output: 2
Why: placing 1 slides 3 once, then placing 2 slides 3 once moreInput: nums = [5, 4, 3, 2, 1]
Output: 10
Why: each new value slides every value already placedInput: nums = [2, 2, 2]
Output: 0
Why: edge case, equal values stay where they areHints
0 / 3
You do not need a formula. The question is about what the algorithm does, so let the algorithm do it and watch.
Work on a copy of the list and run insertion sort on it, keeping a counter next to the line that moves a value one slot right.
For each index from the second onwards, hold its value, and while the value to its left is strictly larger, shift that value right and add one to the counter. Drop the held value into the gap. The counter at the end is the answer.
Solution
Running insertion sort on a copy and counting inside its inner loop answers the question exactly, because every slide is one execution of that loop body. The comparison must be strictly greater than, which is what keeps equal values from sliding and keeps the sort stable. Each slide also fixes one pair of values that appeared in the wrong order, which is why a reversed list costs the most. Time is O(n²) in the worst case and O(n) on a list that is already sorted, and space is O(n) for the copy.
def count_shifts(nums):
a = list(nums) # sort a copy, leave the input alone
shifts = 0
for i in range(1, len(a)):
cur, j = a[i], i - 1
while j >= 0 and a[j] > cur: # only strictly larger values make room
a[j + 1] = a[j]
shifts += 1
j -= 1
a[j + 1] = cur # drop the held value into the gap
return shifts
print(count_shifts([3, 1, 2])) # -> 2
print(count_shifts([5, 4, 3, 2, 1])) # -> 10
print(count_shifts([2, 2, 2])) # -> 0Stuck on the idea rather than the code? Insertion Sort covers it.