Insertion Sort Algorithm

Insertion sort is a sorting algorithm in O(n²) time. It basically inserts each item into its correct position.

Pseudocode

This pseudocode takes a list $a_1, a_2, ..., a_n$.

for i = 2 to n
   value = a at i
   j = i - 1
   while j ≥ 1 and value < a at j
      a at j + 1 = a at j
      j = j - 1
   a at j + 1 = value

This is the code in C (integer list assumed):

void insertion_sort(int* a, int n)
{
   int i, j, value;
   for(i=1;i<n;i++)
   {
      value = a[i];
      j=i-1;
      while(j>=0 && value < a[j])
      {
         a[j+1] = a[j];
         j--;
      }
      a[j+1] = value;
   }
}

 See Also

• Sorting

Sorting algorithms Bubble sort - Insertion sort - Merge sort - Quicksort - Selection sort - Heap sort