Growing with the Web

Insertion sort

Published , updated
Tags:

Insertion sort works by looking at each item in an array (starting with the second) and comparing it with the item before. If the item before is larger, they are swapped. This continues until the item is smaller at which point we do the same for the next item.

Insertion sort example

As you probably guessed, insertion sort isn’t one of the fastest sorts, running in O(n^2) worst case time. It does have a few benefits however:

  • It is faster than most O(n \log n) sorting algorithms for small lists.
  • It is very memory efficient requiring only O(1) auxiliary space for the single item that is being moved.
  • It is a stable sort; equal elements appear in the same order in the sorted list.
  • It is an adaptive sort; it’s fast when sorting mostly sorted lists or when adding items to an already sorted list.
  • It is really easy to implement.

Complexity

Time Space
Worst case Best case Average case Worst case
O(n^2) O(n) O(n^2) O(1) auxiliary

When it’s fast

Sorting 2,3,4,5,1 example

As mentioned above it can be fast under certain circumstances. Consider the array [2,3,4,5,1], when using an algorithm like merge sort we would still need to split all the items and them merge them back up. With insertion sort we just need to verify that [2,3,4,5] are in the correct ‘sorted so far’ order, then we shift all of them up one index for 1.

Being an adaptive sort also makes it an online algorithm, which means we can start sorting before we get all the items and then merge the lists once the partial sorting has completed.

Code

public class InsertionSort<T> : IGenericSortingAlgorithm<T> where T : IComparable
{
    public void Sort(IList<T> list)
    {
        for (int i = 1; i < list.Count; i++) {
            T item = list[i];
            int indexHole = i;
            while (indexHole > 0 && list[indexHole - 1].CompareTo(item) > 0) {
                list[indexHole] = list[--indexHole];
            }
            list[indexHole] = item;
        }
    }
}
public class InsertionSort {
    public static <T extends Comparable<T>> void sort(T[] array) {
        for (int i = 1; i < array.length; i++) {
            T item = array[i];
            int indexHole = i;
            while (indexHole > 0 && array[indexHole - 1].compareTo(item) > 0) {
                array[indexHole] = array[--indexHole];
            }
            array[indexHole] = item;
        }
    }
}
/**
 * Sorts an array using insertion sort.
 * @param {Array} array The array to sort.
 * @param {function} compare The compare function.
 * @returns The sorted array.
 */
function sort(array, compare) {
  for (var i = 1; i < array.length; i++) {
    var item = array[i];
    var indexHole = i;
    while (indexHole > 0 && compare(array[indexHole - 1], item) > 0) {
      array[indexHole] = array[--indexHole];
    }
    array[indexHole] = item;
    if (sortExternal.shiftObserver) {
      sortExternal.shiftObserver(i, indexHole);
    }
  }

  return array;
}
def default_compare(a, b):
  if a < b:
    return -1
  elif a > b:
    return 1
  return 0

def sort(array, compare=default_compare):
  for i in range(1, len(array)):
    item = array[i]
    indexHole = i
    while indexHole > 0 and compare(array[indexHole - 1], item) > 0:
      array[indexHole] = array[indexHole - 1]
      indexHole -= 1
    array[indexHole] = item
  return array
module InsertionSort
  # Sorts an array using insertion sort.
  def self.sort(array, compare = lambda { |a, b| a <=> b })
    (1..array.length - 1).each do |i|
      item = array[i]
      indexHole = i
      while indexHole > 0 and compare.call(array[indexHole - 1], item) > 0
        array[indexHole] = array[indexHole - 1]
        indexHole = indexHole - 1
      end
      array[indexHole] = item
    end
  end
end

Textbooks

Here are two CS textbooks I personally recommend; the Algorithm Design Manual (Steven S. Skiena) is a fantastic introduction to data structures and algorithms without getting to deep into the maths side of things, and Introduction to Algorithms (CLRS) which provides a much deeper, math heavy look.

 

Comments

comments powered by Disqus
Like this article?
Subscribe for more!