Saturday 10 November 2012

Insertion sort

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.

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.
Insertion sort example

Complexity

Time, worst case\(O(n^2)\)
Time, best case\(O(n)\)
Time, average case\(O(n^2)\)
Space, worst case\(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.

Sorting 2,3,4,5,1 example

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

View on GitHub

public static int[] insertionSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        int item = array[i];
        int indexHole = i;
        while (indexHole > 0 && array[indexHole - 1] > item) {
            array[indexHole] = array[--indexHole];
        }
        array[indexHole] = item;
    }
    return array;
}