Fandom

Programmer's Wiki

Insertion sort

406pages on
this wiki
Add New Page
Talk3 Share

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

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.