Sorting Algorithms: Insertion Sort

Insertion Sort  |  Running time O(n²)  and Memory O(1)

It works by taking elements from the list one by one and inserting them in their correct position in the sorted part of the list.

If we have to sort an array of n elements,

- This algorithm makes n passes of the array

- In every pass, it picks up the first element from the unsorted part of array and inserts it in its correct position in the sorted part of array.

- The insertion is done as shown below:

Here the element 4 has to be inserted into its correct position in the sorted (black) partof the array. 

First of all, 4 is picked up from the array and stored in a temporary variable, so that a hole is created.

Now, all the numbers that are smaller than 4 are shifted to right. This is done through a loop.

Then finally 4 is inserted into the empty hole.

Algorithm

//insertion sort in descending order i.e. largest to smallest

for ( i=0; i< n; i++ )      //i controls the number of passes

{    int temp = a[i];

/* Shift to right all elements smaller than temp */

for( j=i; a[j]<temp && j>=0; j-- )

     {    a[j] = a[j-1];

     }

     /* insert temp at the empty hole */

     a[j] = temp; 

} 

Example: We will sort an array in descending order using insertion sort.

Insertion sort is also a time taking technique as its complexity is O(n²).

Note that if the list is almost sorted, then less number of shifts and swaps will be needed, as most of the elements will already be in or close to their correct places. But if the list is fully unsorted, then a large number of shifts and swaps will be needed. This means insertion sort is a good sorting technique to be used when the list is almost sorted.

Also, like other techniques having O(n²) complexity, insertion sort is inefficient if the list is very large (say millions of elements).