Insertion sort

From Algorithmist
Jump to: navigation, search
Sorting
Algorithms
Bubble sort
Insertion sort
Selection sort
Quicksort
Merge sort
Heap sort
Introsort
Counting sort
Problems
Problems solvable using sorting
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 heapsort 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[edit]

  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.

Pseudo-code[edit]

  • 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

References[edit]

  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