Easy difficulty · Algorithm · Topics: sorting, comparison-sort, stable
Insertion sort grows a sorted prefix one element at a time. It takes the next element, slides it left past every larger value, and drops it into the gap. It is simple, stable, in place, and very fast on arrays that are already nearly sorted.
This is how you sort playing cards in your hand: pick up a new card and slide it into the right spot among the cards you already hold, which are kept in order. You never need to look at cards you have not picked up yet.
The invariant: before iteration i, nums[0..i-1] contains the original first i elements in sorted order. Inserting nums[i] into that sorted block keeps the invariant true for i + 1.
i = 1 (a single element is already sorted).key = nums[i] and set j = i - 1.j >= 0 and nums[j] > key, copy nums[j] one slot right (nums[j + 1] = nums[j]) and decrement j.key into nums[j + 1].ii = n - 1Test case 0: nums = [6, 3, 8, 2, 9, 1].
| i | key | Shifts | Array after inserting |
|---|---|---|---|
| 1 | 3 | 6 moves right | [3, 6, 8, 2, 9, 1] |
| 2 | 8 | none | [3, 6, 8, 2, 9, 1] |
| 3 | 2 | 8, 6, 3 move right | [2, 3, 6, 8, 9, 1] |
| 4 | 9 | none | [2, 3, 6, 8, 9, 1] |
| 5 | 1 | 9, 8, 6, 3, 2 move right | [1, 2, 3, 6, 8, 9] |
When no shift is needed (i = 2 and i = 4) the key is already larger than the last sorted element, so the inner loop does not run at all.
| Case | Time | Why |
|---|---|---|
| Best | O(n) | sorted input: each key is compared once and nothing shifts |
| Average | O(n^2) | each key shifts past about half of the sorted prefix |
| Worst | O(n^2) | reverse order: key i shifts past all i earlier elements |
| Space | O(1) | in place, only key and j are stored |
key before shifting; the shift overwrites nums[i].nums[j] > key && j >= 0, which reads nums[-1] first. Check the bound before the value.>= instead of > makes the sort unstable.nums[j] instead of nums[j + 1]; after the loop j points at the element before the gap.i marks the next element to insert; the bars on its left form the sorted prefix.key holds the value being inserted, and j walks left from i - 1.nums[j + 1] = key closes the gap.Input: nums = [6, 3, 8, 2, 9, 1]
Output: [1, 2, 3, 6, 8, 9]
class Solution {
insertionSort(nums) {
const n = nums.length;
// nums[0..i-1] is always sorted; insert nums[i] into it.
for (let i = 1; i < n; i++) {
const key = nums[i];
let j = i - 1;
// Shift larger values one step to the right to open a gap.
while (j >= 0 && nums[j] > key) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = key; // drop the key into the gap
}
return nums;
}
}