/* Insertion Sort */

## Description :

Insertion sort in a sorting algorithm which takes input as array of number
and returns the array in sort order as output.

This algorithm is not something uncommon to the persons who know card playing.
In the game of cards, a player gets 13 cards. He keeps them in the sorted
order in his hand for his ease. A player looks at the first two cards,
sorts them and keeps the smaller card first and then the second.
Suppose that two cards were 9 and 8, the player swap them and keep
8 before 9. Now he takes the third card. Suppose, it is 10,
then it is in its position. If this card is of number 2,
the player will pick it up and put it on the start of the cards.
Then he looks at the fourth card and inserts it in the first three cards
(that he has sorted) at a proper place. He repeats the same process
with all the cards and finally gets the cards in a sorted order. Thus
in this algorithm, we keep the left part of the array sorted and take
element from the right and insert it in the left part at its proper place.
Due to this process of insertion, it is called insertion sorting.

## Program :

## Output :

Written with ♥ from Mangesh.