algorithmfree

Insertion sort

Sort an array by growing a sorted prefix, one element at a time.

time: O(n²)
space: O(1)

// step through it

step 1 / 15

1function insertionSort(nums) {2  for (let i = 1; i < nums.length; i++) {3    const key = nums[i];4    let j = i - 1;5    while (j >= 0 && nums[j] > key) {6      nums[j + 1] = nums[j];7      j--;8    }9    nums[j + 1] = key;10  }11  return nums;12}

key: = 2

Take key = 2. Everything to its left is already sorted.

Tip: use the arrow keys to step.

How it works

Take the next element as the key. Shift every larger element in the sorted prefix one place right, then drop the key into the gap. It is quadratic in the worst case, but very fast on short or nearly sorted arrays, which is why real sort implementations use it for small runs.