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.