**subscribe to the RSS feed**for updates on this topic.

**Insertion sort**is one of the most common sorting algorithms you’ll ever bump into. It is very simple and it takes time roughly equal to

**c*n2**to sort n items, where c is an undependable constant.

**Input:**a sequence of

**n**unsorted numbers.

**Output:**a sequence of

**permuted n**numbers from the input such that those numbers are

**sorted,**most of the time, in decreasing order.

### How it works

Indexes of numbers in this array are present above the rectangles, their connected values, on the other hand, appear in the rectangles. Have in mind that in C++ indexing starts at *zero*, and ends at *length – 1*.

In each iteration, the black rectangle represents **the** **key** taken from the current indexed number in for loop, which is being compared with all values in gray rectangles from it’s left. Gray arrows represent moving gray values one position to the right, and black arrow represent moving the key when appropriate.

### Code realization

1 2 3 4 5 6 7 8 9 |
void insertion_sort(int a[], int length){ int i, j, key; for(i = 1; i = 0 && a[j] > key){ a[j + 1] = a[j]; j--; } a[j + 1] = key; } } |

This function takes two parameters: the “a” array and the “length” integer that represent the number of it’s elements. It goes through the array as shown on the images and repositions it’s values so that you get a sorted array in decreasing order as an output which can be tested using printf function.

There is also a variant for getting the output in non-decreasing order:

1 2 3 4 5 6 7 8 9 10 11 12 |
void inverted_insertion_sort(int a[], int length){ int i, j, key; for(i = length - 2; i >= 0; i--){ key = a[i]; j = i + 1; while(j < key){ a[j - 1] = a[j]; j++; } a[j - 1] = key; } } |

This algorithm is very popular in terms of sorting short arrays, but for more complex situations you should better check out my Algorithms category and find what you need. Also, make sure to understand the code completely by following through the function with your own example and figuring it out. Good luck!

IgorDecember 18, 2013 at 4:19 PMVery good explanation, well explained in detail, I like it. Can I follow you somewhere for recent updates and more articles?

Dušan JovanovićDecember 18, 2013 at 4:23 PMThank you, of course you can follow me to stay up to date, on twitter I’m @dusanjov, you can also subscribe to my RSS feed.