Insertion sort is similar to sorting playing cards.
Start with second element and keep in correct location to its left.
Only difference in programming is all the other elements need to be moved to the right to make place for the incoming element.
It is particularly useful for partially sorted array.
Time complexity : O(n2)
Extra Memory:θ(1)
Stable : Yes
