Insertion sort sorts the way you arrange playing cards in your hand: keep the cards you've already picked up in order, and slide each new card left until it sits in the right place. The front of the array is always sorted, and it grows by one value each step.
nums[0] as a sorted prefix of length 1.Each key is taken out, bigger values shift right, and the key drops into the gap.
function insertionSort(nums) { for (let i = 1; i < nums.length; i++) { const key = nums[i]; // the next value to place let j = i - 1; while (j >= 0 && nums[j] > key) { nums[j + 1] = nums[j]; // shift bigger values one step right j--; } nums[j + 1] = key; // drop the value into the gap } return nums;}The work is the number of shifts, which equals the number of inversions — pairs that are in the wrong order. A reversed array has n(n − 1)/2 of them: O(n²). A sorted array has none, and each key is checked once: O(n). A nearly sorted array, with each value only a few places from home, is close to O(n). Extra space is O(1).
For small arrays (up to a few dozen values) and nearly sorted ones it beats the O(n log n) sorts, because its inner loop is so simple. That's why real libraries use it inside their fast sorts: Python's and Java's Timsort and C++'s introsort switch to insertion sort for short runs.