Insertion Sort

C Implementation of "Insertion Sort"
Insertion Sort:

  1. Has a Time Complexity of O(n^2)
  2. Better than Bubble Sort & Selection Sort
  3. Logic:
    • Divide the array into sorted part & unsorted part
    • Create a hole in unsorted part, and copy that element to a variable 
    • Compare the value with each and every value in unsorted part
    • If the values in the Sorted part is found to be greater than this value, do a shift
    • Place the copied value in the created hole in the sorted part after all the shifts