Insertion Sort

Continuing our sorting algorithm discussion, today’s article will cover a technique known as Insertion Sort.

Insertion sort[1] is a simple, quadratic (O(n2)) sorting algorithm that iterates forward through the array, sorting the current index value in-place by inserting it into the correct position among the values at smaller indices, which were sorted in previous passes. In practice it out performs the other quadratic sorting algorithms, such as Bubble Sort and Selection Sort.

How do it…

Here is a simple insertion sort algorithm in JavaScript:

function insertionSort(a) {
  for (var i = 1, j = a.length, iHole, oItem; i < j; i += 1) {
    oItem = a[i];
    iHole = i;

    while (iHole > 0 && a[iHole - 1] > oItem) {
      a[iHole] = a[iHole - 1];
      iHole -= 1;
    }

    a[iHole] = oItem;
  }
}

Here it is in action:


Restart Insertion Sort With a New Array

Lastly, if we take a 10,000 element array and sort it, here is how insertion sort compares to native array sort (prints to the console):

Insertion Sort Comparison Tests

How it works…

The insertion sort algorithm moves forward through the array, starting at index n=1. It removes the value of the nth element from the array and then starts comparing the removed value to the values at indices less than n (well denote this as n-k, where k starts at 1). At each step the algorithm compares the removed value to the value at n-k. If the n-k value is greater, the value at n-k moves to index n-(k+1), otherwise the removed value is inserted at index n-(k+1). This comparison keeps happening until the removed value is swapped in or the beginning of the array is reached, and the value is inserted at the first index.

There are variations of insertion sort, but they change the algorithm enough that they have their own unique names and will be discussed separately. Of the quadratic sorting algorithm, insertion sort tends to outperform its peers, because the inner loop usually visits less nodes. If you run the comparison test, you will see that insertion sort is 5-10x slower (depending on browser and random sort order) when sorting a 10,000 value array than the native sorting algorithm.


References

  1. Insertion Sort Wikipedia article