Insertion sort, is an efficient algorithm for sorting a small number of elements.

Insertion sort works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand.

To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left.

Here is the pseudocode for it.


Here is the python version of it

  for j in range(1, len(a)):  
      key = a[j]
      i = j - 1
      while (i > -1 and a[i] > key): 
          a[i + 1] = a[i]
          i = i - 1
      a[i + 1] = key
     

  return a


a = [6, 5, 3, 1, 8, 7, 2, 4] 
print insertionSort(a)

Hope this helps :)