FANDOM


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

PseudocodeEdit

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 Edit

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

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.