Implement insertionSort(array) — sort an array of numbers ascending using insertion sort. The idea is the one you use without thinking when you pick up a hand of playing cards: you keep the cards in your hand sorted, and each new card you draw slides left past the bigger cards until it sits in the right place. You grow a sorted region one element at a time, inserting each new element where it belongs.
// array: number[] — the numbers to sort. Treated as read-only.
// returns: number[] — a NEW array with the same numbers in ascending order.
// The input is not mutated.
function insertionSort(array: number[]): number[];insertionSort([3, 1, 2]);
// → [1, 2, 3]insertionSort([2, 2, 1]);
// → [1, 2, 2][10, 2] sorts to [2, 10], not [10, 2]. Compare the numbers directly — don't lean on the default Array.prototype.sort, which compares as strings.[]; a single element returns itself; an already-sorted array comes back in the same order; duplicates and negative numbers all work..sort().You'll grow a sorted region one element at a time, sliding each new element left until it lands in its correct slot.
Picture sorting a hand of playing cards. You hold the cards you've already arranged in order on the left. You draw the next card and slide it leftward, comparing it to each card already in your hand, until you reach a card that isn't bigger than it — that's where it goes. You repeat until the deck is empty and your whole hand is sorted. Insertion sort is exactly that: the front of the array is a growing sorted region, and each pass takes the next element and inserts it into that region.
Hold three things in your head: the sorted prefix at the front of the array, the key — the next element you're inserting — and the gap that opens up as you shift bigger elements out of the way. A single element is already a sorted prefix of length one, so you start the work at index 1. For each key, you compare it to the elements in the prefix from right to left. Every element bigger than the key gets copied one slot to the right, which walks an empty gap leftward. The moment you hit an element that is not bigger than the key — or you run off the front of the array — the gap is where the key belongs. Drop it in.
The natural first instinct is to literally "remove the element and re-insert it" using array methods. Find where the key belongs, then splice it out and splice it back in:
function insertionSort(array) {
const arr = array.slice();
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
// Find the first sorted slot whose value is greater than key.
let pos = 0;
while (pos < i && arr[pos] <= key) pos++;
arr.splice(i, 1); // remove key from where it is
arr.splice(pos, 0, key); // re-insert it at its sorted position
}
return arr;
}This produces the right answer, but it's doing far more work than it looks. Each splice has to physically shift every element after the splice point to close or open a gap — so a single insertion can touch the whole array twice (once to remove, once to re-insert). It also obscures the actual idea behind two library calls. The classic version does the shifting itself, in one tight loop, with no allocation per step.
function insertionSort(array) {
// Sort a COPY so the caller's array is never mutated.
const arr = array.slice();
// arr[0] alone counts as a sorted prefix of length 1, so start at index 1.
for (let i = 1; i < arr.length; i++) {
const key = arr[i]; // the card we're inserting into the sorted prefix
let j = i - 1; // walk leftward from the end of the sorted prefix
// Slide every element STRICTLY greater than key one slot to the right,
// opening a gap. `>` (not `>=`) is what makes the sort stable: an element
// equal to key never moves, so equal values keep their original order.
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// j either fell off the front (-1) or stopped on a value <= key.
// The gap is at j + 1 — drop the key in.
arr[j + 1] = key;
}
return arr;
}
module.exports = { insertionSort };The shift is the whole trick. Instead of removing and re-inserting, you save the key in a variable, then copy each larger neighbor one slot to the right with arr[j + 1] = arr[j]. That overwrites the slot the key used to occupy — which is fine, because the key is safe in key. When the loop stops, j + 1 is the now-empty gap, and you write the key there. No splice, no per-step allocation, and the while condition does both jobs at once: stop at the front of the array (j >= 0) or stop when the neighbor isn't bigger (arr[j] > key).
Trace insertionSort([5, 3, 4]). We sort a copy, so the input stays [5, 3, 4].
arr = [5, 3, 4]
i = 1 key = 3 j = 0
arr[0] = 5 > 3 → copy 5 right: arr = [5, 5, 4], j = -1
j < 0, stop → arr[0] = key: arr = [3, 5, 4]
i = 2 key = 4 j = 1
arr[1] = 5 > 4 → copy 5 right: arr = [3, 5, 5], j = 0
arr[0] = 3 > 4? no, stop → arr[1] = key: arr = [3, 4, 5]
return [3, 4, 5]
The diagram below traces a longer insertion — placing 4 into the prefix [1, 3, 5, 8] — so you can watch the gap walk left one copy at a time until the key fits.
array directly sorts the caller's array out from under them. Start with const arr = array.slice() (or [...array]) and sort that. A test compares the input against a snapshot.>= instead of > in the shift. With arr[j] >= key, equal elements would shift past each other and the sort would no longer be stable — two equal values could swap relative order. Use arr[j] > key so equal elements stay put.arr[j] > key without j >= 0, then inserting a new minimum reads arr[-1] (which is undefined) and the comparison misbehaves. The j >= 0 term must come first so the && short-circuits before the out-of-bounds read.i = 0. Index 0 is already a sorted prefix of one element; there's nothing to its left to insert against. Start at i = 1. (Starting at 0 isn't wrong here, just wasted work — j is immediately -1.)array.sort(). The default sort coerces elements to strings, so [10, 2] becomes [10, 2], not [2, 10]. The insertion-sort comparison is numeric (arr[j] > key), so this class of bug can't happen — but only if you implement the loop rather than delegating to .sort().while never runs its body — one comparison per element and you're done. That linear best case is why insertion sort is often used as the base case inside faster sorts (e.g. timsort runs insertion sort on small runs).>, equal elements never cross — insertion sort is stable. Stability lets you sort by one key and then another without scrambling the first ordering (sort people by name, then by age, and equal-age people stay name-ordered).Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.
Implement insertionSort(array) — sort an array of numbers ascending using insertion sort. The idea is the one you use without thinking when you pick up a hand of playing cards: you keep the cards in your hand sorted, and each new card you draw slides left past the bigger cards until it sits in the right place. You grow a sorted region one element at a time, inserting each new element where it belongs.
// array: number[] — the numbers to sort. Treated as read-only.
// returns: number[] — a NEW array with the same numbers in ascending order.
// The input is not mutated.
function insertionSort(array: number[]): number[];insertionSort([3, 1, 2]);
// → [1, 2, 3]insertionSort([2, 2, 1]);
// → [1, 2, 2][10, 2] sorts to [2, 10], not [10, 2]. Compare the numbers directly — don't lean on the default Array.prototype.sort, which compares as strings.[]; a single element returns itself; an already-sorted array comes back in the same order; duplicates and negative numbers all work..sort().You'll grow a sorted region one element at a time, sliding each new element left until it lands in its correct slot.
Picture sorting a hand of playing cards. You hold the cards you've already arranged in order on the left. You draw the next card and slide it leftward, comparing it to each card already in your hand, until you reach a card that isn't bigger than it — that's where it goes. You repeat until the deck is empty and your whole hand is sorted. Insertion sort is exactly that: the front of the array is a growing sorted region, and each pass takes the next element and inserts it into that region.
Hold three things in your head: the sorted prefix at the front of the array, the key — the next element you're inserting — and the gap that opens up as you shift bigger elements out of the way. A single element is already a sorted prefix of length one, so you start the work at index 1. For each key, you compare it to the elements in the prefix from right to left. Every element bigger than the key gets copied one slot to the right, which walks an empty gap leftward. The moment you hit an element that is not bigger than the key — or you run off the front of the array — the gap is where the key belongs. Drop it in.
The natural first instinct is to literally "remove the element and re-insert it" using array methods. Find where the key belongs, then splice it out and splice it back in:
function insertionSort(array) {
const arr = array.slice();
for (let i = 1; i < arr.length; i++) {
const key = arr[i];
// Find the first sorted slot whose value is greater than key.
let pos = 0;
while (pos < i && arr[pos] <= key) pos++;
arr.splice(i, 1); // remove key from where it is
arr.splice(pos, 0, key); // re-insert it at its sorted position
}
return arr;
}This produces the right answer, but it's doing far more work than it looks. Each splice has to physically shift every element after the splice point to close or open a gap — so a single insertion can touch the whole array twice (once to remove, once to re-insert). It also obscures the actual idea behind two library calls. The classic version does the shifting itself, in one tight loop, with no allocation per step.
function insertionSort(array) {
// Sort a COPY so the caller's array is never mutated.
const arr = array.slice();
// arr[0] alone counts as a sorted prefix of length 1, so start at index 1.
for (let i = 1; i < arr.length; i++) {
const key = arr[i]; // the card we're inserting into the sorted prefix
let j = i - 1; // walk leftward from the end of the sorted prefix
// Slide every element STRICTLY greater than key one slot to the right,
// opening a gap. `>` (not `>=`) is what makes the sort stable: an element
// equal to key never moves, so equal values keep their original order.
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
// j either fell off the front (-1) or stopped on a value <= key.
// The gap is at j + 1 — drop the key in.
arr[j + 1] = key;
}
return arr;
}
module.exports = { insertionSort };The shift is the whole trick. Instead of removing and re-inserting, you save the key in a variable, then copy each larger neighbor one slot to the right with arr[j + 1] = arr[j]. That overwrites the slot the key used to occupy — which is fine, because the key is safe in key. When the loop stops, j + 1 is the now-empty gap, and you write the key there. No splice, no per-step allocation, and the while condition does both jobs at once: stop at the front of the array (j >= 0) or stop when the neighbor isn't bigger (arr[j] > key).
Trace insertionSort([5, 3, 4]). We sort a copy, so the input stays [5, 3, 4].
arr = [5, 3, 4]
i = 1 key = 3 j = 0
arr[0] = 5 > 3 → copy 5 right: arr = [5, 5, 4], j = -1
j < 0, stop → arr[0] = key: arr = [3, 5, 4]
i = 2 key = 4 j = 1
arr[1] = 5 > 4 → copy 5 right: arr = [3, 5, 5], j = 0
arr[0] = 3 > 4? no, stop → arr[1] = key: arr = [3, 4, 5]
return [3, 4, 5]
The diagram below traces a longer insertion — placing 4 into the prefix [1, 3, 5, 8] — so you can watch the gap walk left one copy at a time until the key fits.
array directly sorts the caller's array out from under them. Start with const arr = array.slice() (or [...array]) and sort that. A test compares the input against a snapshot.>= instead of > in the shift. With arr[j] >= key, equal elements would shift past each other and the sort would no longer be stable — two equal values could swap relative order. Use arr[j] > key so equal elements stay put.arr[j] > key without j >= 0, then inserting a new minimum reads arr[-1] (which is undefined) and the comparison misbehaves. The j >= 0 term must come first so the && short-circuits before the out-of-bounds read.i = 0. Index 0 is already a sorted prefix of one element; there's nothing to its left to insert against. Start at i = 1. (Starting at 0 isn't wrong here, just wasted work — j is immediately -1.)array.sort(). The default sort coerces elements to strings, so [10, 2] becomes [10, 2], not [2, 10]. The insertion-sort comparison is numeric (arr[j] > key), so this class of bug can't happen — but only if you implement the loop rather than delegating to .sort().while never runs its body — one comparison per element and you're done. That linear best case is why insertion sort is often used as the base case inside faster sorts (e.g. timsort runs insertion sort on small runs).>, equal elements never cross — insertion sort is stable. Stability lets you sort by one key and then another without scrambling the first ordering (sort people by name, then by age, and equal-age people stay name-ordered).Keep practising the same patterns with a nearby challenge.
No submissions yet
Share your approach and start the discussion.