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


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;
      value = a[i];
      while(j>=0 && value < a[j])
         a[j+1] = a[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.