# 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.

blog comments powered by Disqus