Count Insertion Sort Shifts
Given an integer array nums, return the total number of shifts insertion sort would perform while sorting nums in non-decreasing order. A shift happens every time a value already in the sorted prefix is moved one slot right to make room for the next key. This total is the same as the number of inversions in the array.
Constraints
- 0 ≤ nums.length ≤ 1000
- -1000 ≤ numsi ≤ 1000
Example
Input
nums = [2, 4, 1, 3, 5]Output
3Explanation Inserting 1 shifts past 4 and 2 (2 shifts), and inserting 3 shifts past 4 (1 shift) — 3 shifts total.
In plain terms
- Inversion
- A pair of indices i < j where numsi > numsj — the two values are out of order relative to each other.
Count every shift as the sorted prefix grows
02
14
21
33
45
Statusinit
Key = 4. Compare with 2 — already bigger, 0 shifts. Total shifts: 0.
What happens in this step
key = nums[1] = 4, compare nums[0] = 2 2 > 4 is false → 0 shifts array unchanged: [2, 4, 1, 3, 5] 4 is already bigger than everything before it, so nothing moves. Running total: 0.
Step 1 of 4
Steps to visualize
- Run insertion sort as usual, growing the sorted prefix one key at a time.
- Every time a value in the prefix is shifted one slot right, add one to the running total.
- Continue until every key has been inserted.
- Return the running total — it equals the number of inversions in the original array.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
02
14
21
33
45
Statusinit
Key = 4. Compare with 2 — already bigger, 0 shifts. Total shifts: 0.
What happens in this step
key = nums[1] = 4, compare nums[0] = 2 2 > 4 is false → 0 shifts array unchanged: [2, 4, 1, 3, 5] 4 is already bigger than everything before it, so nothing moves. Running total: 0.
Step 1 of 4
Solution
function countInsertionSortShifts(nums) {
let shifts = 0;
for (let i = 1; i < nums.length; i++) {
const key = nums[i];
let j = i - 1;
while (j >= 0 && nums[j] > key) {
nums[j + 1] = nums[j];
j--;
shifts++;
}
nums[j + 1] = key;
}
return shifts;
}- Time
- O(n^2)
- Space
- O(1)
Test cases
| Input | Expected | Covers |
|---|---|---|
nums = [2, 4, 1, 3, 5] | 3 | example from the docstring |
nums = [1, 2, 3, 4] | 0 | no inversions, zero shifts |
nums = [4, 3, 2, 1] | 6 | maximum inversions, n(n-1)/2 shifts |
nums = [5] | 0 | smallest valid input, a single element |
nums = [] | 0 | empty array has no shifts |
nums = [2, 2, 2] | 0 | equal values never trigger a shift |
nums = [1, 3, 2] | 1 | exactly one out-of-order pair |