## 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