/Insertion sort

## Insertion sort

Insertion sort is one efficient Sorting algorithms.It’s a sort in place algorithm.
it’s like sorting cards, you start from the left and compare the first card with the next till you reach the end, finally you put your card in the right position and start over from the 2nd card…etc
so if you have an array like so
[4,2,7,8,1,3,9] , You will start with dividing your array into two half 1- a sorted array 2- unsorted array
and start from the left.
so we will start with the first element and check if it is sorted and since it’s only one comparable object then it’s sorted
and then we move to the 2nd element which is  and check if it is smaller than the element before which is  then since it is smaller we will start indenting the first element one index to the right and store my value which is  so the array will look like so. [4,4,7,8,1,3,9]
then we move the value i am handling into the position of the element i compared to so the array will look like [2,4,7,8,1,3,9]
and since there is nothing more to compare to we will start over from the 3rd element which is . and so we compare with the previous element which is 4 and it’s bigger so we skip it to the previous element which is  and we skip it too because 7 is bigger so we start over from the 4th position and so on till we have a sorted array.
Enough talking and let’s move to the code
the pesudocode is like so Since we have a sequence A we will loop from the 2nd element till n(the array most right element index number)
key is what holds the element i am using or sorting.
i = j-1 i is the value which will count the loops on the sequence to sort one element so we will start from the value we will sort previous element.
so index of the previous element = the index of current element -1 and so we will start a while loop with 2 conditions so if A[i] > key is what we care for the other is just a boundary condition. so since the left half is always sorted so if we meet a[i] > key . this means that my value is less than some value in the sorted left array. so we should replace it by indenting the a[i] right e. and we decrement i to check the previous element and if bigger we indent it too. so on until we meet an element which is smaller than my key then we put the key in the index we stopped on.
there is the algorithm in java it’s also the same in C++.