Insertion Sort

This is an insanely inefficient but simple to implement sorting algorithm. The analogy for this algorithm can be drawn from the card game. Imagine the cards lying face down on the table. You pick cards one by one from the table and arrange them in a sorted order in your hand. For every card after the second card picked, put that card in its right place by comparing that card with the cards in your hand from right to left.

Time Complexity: Average and Worst Case is O(n^2)

                 Best Case is O(n)

Space Complexity: O(1)