Insertion Sort
Where a bubble sort relies on a number of small swaps, insertion sort relies on inserting a single element in the right for a given iteration. Every iteration through the collection leaves a greater segment sorted.
Implementation
function sort(values) {
var length = values.length;
for(var i = 1; i < length; ++i) {
var temp = values[i];
var j = i - 1;
for(; j >= 0 && values[j] > temp; --j) {
values[j+1] = values[j];
}
values[j+1] = temp;
}
};
sort([7, 4, 5, 2, 9, 1]);
//finished
Example
Click step to sort the array.
7
4
5
2
9
1
step
Characteristics
Like bubble sorts, insertion sorts is efficient for an already sorted or nearly sorted collection. Insertion sort will always be at least as efficient as a bubble sort.
In The Real World
Insertion sort is a good choice for small or mostly sorted collections. It performs well, has little memory overhead and is simple to understand and implement.