FANDOM

406 Pages

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

Visual exampleEdit

Suppose we would sort a list:

 3 1 2 0

value = 1

We will start with the second value, 1. The idea is, starting from the item before the current value, we would insert the current value to its correct position in the list. Note that after the ith iteration, the first i elements would be already sorted. (At the nth iteration, all n elements should be sorted, which is the expected output) Now since 1 is less than 3, we will make way for the insert.

 3 3 2 0

value = 1

The loop ends since there are no more items to compare with.

 1 3 2 0
value = 2

Now compare 3 and 2. The value 3 would now make way for insertion.

 1 3 3 0
value = 2

Now since 1 < 2, 2 will now be inserted at the correct position.

 1 2 3 0

The value 0 would then be inserted at the start of the list:

value = 0
 1 2 3 3 1 2 2 3 1 1 2 3 0 1 2 3

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;
}
}
```
Sorting algorithms
Bubble sort - Insertion sort - Merge sort - Quicksort - Selection sort