Insertion Sort

        Insertion Sort merely means that we insert one number at a time into its correct position comparing with the numbers to the left of it. At each iteration, the key value is compared to the values at its left and swapped if necessary.

Insertion_Sort (Ascending order):
1.  for j = 2 to A.length
2.     key = A[j]
3.     i = j - 1
4.     while i>0 and A[i]>key
5.         A[i+1] = A[i]
6.         i = i - 1
7.     A[i+1] = key

Here j is the index of our key and A is our list or array containing the unsorted numbers. i is our index to store previous value.

        We initialize the for loop from second position so as to skip the first which will be our initial key. In the (2) line we store our current key and at (3) we store the previous value or the value left of the key. At (4) we compare the value at the left of the key with the key. If the key is smaller than the value to its left, we swap both values. (5) handles the swapping of positions of the left side values (6) decrements the i. The while loop keeps on executing till there is no value greater than the key at the left of the key. At (7) we position the key at the right place. This goes on for each value in the array.

There is a Python implementation of insertion sort at the following Gist (both in ascending and descending order). For descending order, the only change is at (4) for loop while comparing.

Insertion sort is best suitable for small datasets and is inefficient for large datasets to sort. The best case performance for this algorithm is where the input is already sorted and its linear running time will be O(n). The worst case performance would be where the input is sorted in the reverse order O(n²).