Count Insertion Sort Shifts

1. Define the problem

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 ≤ nums_i ≤ 1000

Example

Inputnums = [2, 4, 1, 3, 5]

Output3

Explanation Inserting 1 shifts past 4 and 2 (2 shifts), and inserting 3 shifts past 4 (1 shift) — 3 shifts total.

2. Know the words first

In plain terms

Inversion: A pair of indices i < j where nums_i > nums_j — the two values are out of order relative to each other.

3. Visualize the solution

Count every shift as the sorted prefix grows

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.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Count every shift as the sorted prefix grows

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

5. Solution

Solution

solution.tsTypeScript

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)

6. Test cases

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

Count Insertion Sort Shifts