Intro: Insertion sort is a sorting algorithm that builds the final sorted list one item at a time. It is less efficient on large lists than more advanced algorithms such as quick, heap or merge sort. It maintains a sorted sublist in the lower positions of the list. Each new item is then “inserted” back into the previous sublist such that the sorted sublist is one item larger.

Pseudo Code:

  1. If it is the first element, it is already sorted. return 1;
  2. Pick next element
  3. Compare with all elements in the sorted sublist
  4. Shift all the elements in the sorted sublist that are greater than the value to be sorted
  5. Insert the value
  6. Repeat until list is sorted

Detailed:

procedure insertionSort( A : array of items )
   int holePosition
   int valueToInsert

   for i = 1 to length(A) inclusive do:

      /* select value to be inserted */
      valueToInsert = A[i]
      holePosition = i

      /*locate hole position for the element to be inserted */

      while holePosition > 0 and A[holePosition-1] > valueToInsert do:
         A[holePosition] = A[holePosition-1]
         holePosition = holePosition -1
      end while

      /* insert the number at hole position */
      A[holePosition] = valueToInsert

   end for

end procedure
   Set lowerBound = 1
   Set upperBound = n 

   while x not found
      if upperBound < lowerBound 
         EXIT: x does not exists.

      set midPoint = lowerBound + ( upperBound - lowerBound ) / 2

      if A[midPoint] < x
         set lowerBound = midPoint + 1

      if A[midPoint] > x
         set upperBound = midPoint - 1 

      if A[midPoint] = x 
         EXIT: x found at location midPoint

   end while

end procedure