Insertion Sort

Insertion sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there, repeating until no input remains.

A graphical example of insertion sort is as under:

From the below animation it can be seen that Insertion sort works fastest for nearly sorted array of elements. The time required to sort the elements increases in the order: few unique, random and then reversed.

What are random, nearly sorted, reversed and few unique elements?

  1. Random: {6, 9, 5, 8, 7, 4, 2, 1, 3}
    Here all the elements are arranged in a random fashion.
  2. Nearly sorted: {5, 6, 7, 8, 9, 1, 2, 3, 4}
    The array is nearly sorted. For example, the above array if divided into two, are sorted individually.
  3. Reversed: {9, 8, 7, 6, 5, 4, 3, 2, 1}
    The array elements are reverse sorted and we are supported to sort them in ascending order.
  4. Few Unique: {1, 1, 2, 9, 4, 3, 2, 5, 9, 6}
    The array contains duplicate entries.
Random Nearly Sorted Reversed Few Unique

Key

  1. Black values are sorted.
  2. Gray values are unsorted.
  3. A red triangle marks the algorithm position.

Algorithm

for i = 1 to length(A) - 1
   x = A[i]
   j = i
   while j > 0 and A[j-1] > x
      A[j] = A[j-1]
      j = j - 1
   A[j] = x


Implementation:

/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;
 
       /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */
       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}
 

Analysis 

The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., O(n)). During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.

The simplest worst case input is an array sorted in reverse order. The set of all worst case inputs consists of all arrays where each element is the smallest or second-smallest of the elements before it. In these cases every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. This gives insertion sort a quadratic running time (i.e., O(n2)).

The average case is also quadratic, which makes insertion sort impractical for sorting large arrays. However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quick sort.

Auxiliary Space: O(1)
Sorting In Place: Yes
Stable: Yes

Insertion sort is uses when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.

Source: Wikipedia