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

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.

 

More posts tagged Sorting