Implement Insertion Sort
Given an integer array nums, sort it in non-decreasing order using insertion sort , without calling a built-in sort function. Grow the sorted prefix one value at a time: for each key, shift every bigger value in the sorted prefix one slot right, then drop the key into the gap it leaves behind.
Constraints
- 1 ≤ nums.length ≤ 1000
- -1000 ≤ numsi ≤ 1000
Example
Input
nums = [5, 2, 9, 1, 5, 6]Output
[1, 2, 5, 5, 6, 9]Explanation Each value is inserted into its correct spot among the values already placed to its left.
In plain terms
- Sorted prefix
- The part of the array, starting at index 0, that is already in order.
- Key
- The next unsorted value, about to be inserted into the sorted prefix.
Grow the sorted prefix by inserting one key at a time
05
12
29
31
45
56
Statusinit
Sorted prefix: [5]. Key = 2.
What happens in this step
nums = [5, 2, 9, 1, 5, 6] sorted prefix = [5], key = nums[1] = 2 A single value is trivially sorted. The next value, 2, becomes the key about to be inserted.
Step 1 of 5
Steps to visualize
- Start with a sorted prefix of length 1 — a single value is trivially sorted.
- Take the next value as the key.
- Shift every bigger value in the sorted prefix one slot right.
- Drop the key into the gap once a smaller value is found or the prefix start is reached.
- Repeat until every value has been inserted.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
05
12
29
31
45
56
Statusinit
Sorted prefix: [5]. Key = 2.
What happens in this step
nums = [5, 2, 9, 1, 5, 6] sorted prefix = [5], key = nums[1] = 2 A single value is trivially sorted. The next value, 2, becomes the key about to be inserted.
Step 1 of 5
Solution
function insertionSort(nums) {
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--;
}
nums[j + 1] = key;
}
return nums;
}- Time
- O(n^2)
- Space
- O(1)
Test cases
| Input | Expected | Covers |
|---|---|---|
nums = [5, 2, 9, 1, 5, 6] | [1, 2, 5, 5, 6, 9] | example from the docstring |
nums = [1, 2, 3, 4] | [1, 2, 3, 4] | best case, no shifting needed at all |
nums = [5, 4, 3, 2, 1] | [1, 2, 3, 4, 5] | worst case, every key shifts past everything before it |
nums = [7] | [7] | smallest valid input, a single element |
nums = [3, 1, 2, 3, 1] | [1, 1, 2, 3, 3] | repeated values mixed throughout |
nums = [-3, 5, -1, 0, -2] | [-3, -2, -1, 0, 5] | negative and positive values mixed together |