home

linear search

arrays

linked lists

hash tables

binary search

bubble sort

insertion sort

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