Insertion Sort
Introduction
Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands.
How does it work?
The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.
begin insertionSort(list)
n = length(list)
for i = 1 to n - 1 do
j = i
while j > 0 and list[j-1] > list[j] do
swap(list[j], list[j-1])
j = j - 1
end while
end for
end insertionSort
Step By Step
Implementation (JavaScript)
function insertionSort(values) {
for (let i = 0; i < values.length; i++) {
let j = i;
while(j > 0 && values[j - 1] > values[j]) {
let temp = values[j];
values[j] = values[j - 1];
values[j - 1] = temp;
j--;
}
}
}