Insertion Sort

Insertion sort is also very simple sorting algorithm. The working of insertion sort is similar as we sort playing cards in our hand.While playing cards we assume that first card is sorted and then select one card from unsorted cards. If the selected card is greater than the sorted card place it on left otherwise place it on right.Similarly select all unsorted cards and place them at there exact location.

The same technique is applied in insertion sort.

Algorithm

Following are the simple steps to sort array using insert sort:

Step 1-  Pick the first element, assume that it is already sorted. Store it in sorted array

Step 2- Pick the next element, and store it in separate variable say ‘key.

Step 3 – Now, compare the key with all elements in the sorted array.

Step 4 – If  elements in the sorted array are smaller than the current element key, then move to the next element. Else, insert key element in the sorted array at its exact location.

Step 5 – Repeat until the array is sorted.

Working of Insertion Sort

To understand the working of insertion sort lets take an unsorted array named A having elements

15 33 22 7 39 19