Insertion sort

This is a stub or unfinished. Contribute by editing me.

Insertion sort is a simple sorting algorithm that is asymptotically equivalent to bubble sort, but is much faster in practice, because the number of swaps is at most linear. Its complexity is $O(n^{2})$, in-place, and is stable.

Insertion sort is preferable when the number of items is small - the constant is small enough that the benefit due to excellent locality and noticably better when the entire list fits in the lower levels of caching. Insertion sort is also quick when the list is nearly sorted. Introsort exploits these properties by using this sort after quicksort or heap sort have made a few passes on the list.

Insertion sort in an array with gaps can achieve the theoretical lower bound of $O(n\log n)$ of sorting with high probability. (Bender, Farach-Colton, Mosteiro, 2004)

Algorithm

1. Iterate through the array, starting from the second element:
   1. Note the element at this index.
   2. Walk back through the previous elements until you find a smaller element (or the beginning of the array), moving each element up by one.
   3. Insert the noted element at this point.

Pseudocode

• a is an array of size N

for i from 1 to N
   key = a[i]
   j = i - 1
   while j >= 0 and a[j] > key
      a[j+1] = a[j]
      j = j - 1
   a[j+1] = key
next i

C#

int key, j;

for (int x = 1; x < array.Length; x++)
{
    key = array[x];
    j = x - 1;

    while (j >= 0 && array[j] > key)
    {
        array[j + 1] = array[j];
        j = j - 1;
    }

    array[j + 1] = key;
}

References

1. Cormen, Leiserson, Rivest, Stein, "Introduction to Algorithms", 2nd Ed. MIT Press 2001, pp17-18
2. Bender, Farach-Colton, Mosteiro, "INSERTION SORT is O(n log n)", 2004, http://citeseer.ist.psu.edu/bender04insertion.html