Theory
Insertion Sort builds the sorted portion of an array one element at a time. Each new element is compared with previous elements and inserted into the correct position. It performs well on small or nearly sorted arrays.
Example
const numbers = [5, 3, 4, 1];
for (let i = 1; i < numbers.length; i++) {
const key = numbers[i];
let j = i - 1;
while (j >= 0 && numbers[j] > key) {
numbers[j + 1] = numbers[j];
j--;
}
numbers[j + 1] = key;
}
console.log(numbers);
Expected Output
[1, 3, 4, 5]
Practice
Implement Insertion Sort and test it on an already sorted array.
Interview Questions
- How does Insertion Sort work?
- When is Insertion Sort efficient?
- What is its worst-case complexity?
- Is Insertion Sort stable?