Insertion sort is one of the many algorithms that we will cover in this blog. I choose this algorithm to start with because I think that this is a fairly easy to understand (better start with an easy one :) )

To understand the insertion sort imagine that you have a deck of cards that is not sorted. You put this deck of cards on the table and start picking a card one by one; each time putting the card in your left hand. Each time you pick a card you must compare that card with the previous cards until you find a card that is greater than the one you have. By doing so you just sorted the deck of cards on your left hand.

Insertion sort is quite similar. Basically you have a list and you start looping linearly through that list, each time checking with the previous items if the selected item (the key) is smaller than the items before it. If so move that item forward. If the previous item is smaller then you stop checking.

The below figures should make this more clear. (I will refer to the item being sorted as the *key.*

**(FIG 1)** *Start from the element “2″. Check it with the previous element “5″. Since “5″ > “2″, move “5″ forward (Result shown in Fig 2).*

**(FIG 2)** *Select the next element “4″. Check it with the previous element “5″. Since “5″ > “4″, move “5″ forward. Check “4″ with “2″. Since “2″ < “4″ then “2″ should not move and thus we stop checking with previous values. Move “4″ to the proper index (Result shown in Fig 3)*

**(FIG 3)**Select the next element “6″. Check it with the previous element “5″. Since “5″ < “6″, “5″ should not move and *thus we stop checking with previous values (Result shown in Fig 4)*

* ***(FIG 4)***Select the next element “1″. Check it with the previous element “6″. Since 6 > 1 move 6 forward. Check the key(“1″) with the other item “5″ since “5″ > “1″, move “5″ forward. continue the same process with all other elements (Result shown in Fig 5)*

As you can see from the figures above the insertion sort is very simple. Lets now try it out in C#

1: //unsorted array

2: int[] list = new int[] { 5, 2, 4, 6, 1 };

` 3:`

4: // the key element being sorted

5: int key;

` 6:`

7: //start looping starting from the second element

8: for (int i = 1; i < list.Length; i++)

` 9: {`

10: key = list[i];//store the key

11: int j = i - 1;//get the previous index

` 12:`

13: //loop until you meet a smaller number or 0

14: while (j >= 0 && list[j] > key)

` 15: {`

16: //move the greater number forward

` 17: list[j + 1] = list[j];`

18: //decrement the counter so that we get the previous element

` 19: j--;`

` 20: }`

21: //set the key in the proper index

` 22: list[j + 1] = key;`

` 23: }`

### Conclusion

The insertion sort is a fairly efficient algorithm for sorting small arrays. As you could see in the above explanation you must compare the *key *with all other elements that are in front of the key (This could suffer performance with large arrays)

**The best case scenario** for this algorithm would be if the elements in the array are already sorted. This would give us the best performance because there would be no need to compare the *key *with all the other element in front of it.

**The worse case scenario** would be if the array is in reverse order. This would force us check each element every time.

I hope I gave a good explanation of this algorithm. Feel free to leave comments/suggestions….

P.S This is my first algorithms article so please be kind; I promise I’ll try to improve :D

Nice. Was appropriate that the first blog insertion would be about the insertion sort. The figures are a nice touch. Will definitely check this blog out again.

thanks dude

Hi Marlon,

I think this blog is a great idea, keep it up.

A comment on the algo: probably the use of a linked list would help explaining better how insertion sort works.

Well done master!

Good work!!!

————————————-

http://simply-url.blogspot.com