Insertion Sort Shifts

Insertion sort takes the values one at a time and slides each one left into its place among the values before it, like sorting playing cards in your hand.

shifts = 0
for i in range(1, len(a)):
    key = a[i]
    j = i - 1
    while j >= 0 and a[j] > key:
        a[j + 1] = a[j]   # shift one place right
        shifts += 1
        j -= 1
    a[j + 1] = key

Return the final value of shifts: how many times a value was shifted one place to the right. Equal values do not move past each other, because the loop only shifts values that are strictly greater than key.

Examples

Example 1

Input:

insertion_sort_shifts([3, 1, 2])

Output:

2

1 shifts the 3 once, then 2 shifts the 3 once: 2 shifts.

Example 2

Input:

insertion_sort_shifts([5, 4, 3, 2, 1])

Output:

10

A reversed list of 5 has the most: 10 shifts.

Constraints

• 0 <= len(nums) <= 2000
• -10**9 <= nums[i] <= 10**9