Insertion sort algorithm and analysis
Content covered: 

Insertion Sort:
Insertion sort is based on the card game in which we sort the playing cards in our hand. In this sorting, each time we compare the element to be inserted in sorted subarray and find it's right position before inserting it.

Insertion_Sort (A)
  for j=2 to A.length
  Key = A[j]
  // insert A[j] into sorted sequence A[1.......j-1]
  while (i>0 and A[i] > Key)
       A[i+1] = A[i]
       i = i-1
   A[i+1] = key

Time Complexity:
Best Case: O(n)
Average Case: O(n2)
Worst Case: O(n2)

More Less