Definition
The 1st element is assumed to be sorted and the iteration starts from the second element towards the end. The difference in this algorithm compared to Bubble Sort,
it compares the element that are on the left of it. It all means that the sorting goes not forward, but backwards from the right to the left.
This algorithm is sufficient on smaller data sets like Bubble Sort, because its Time complexity is O(n2).
In the implementations of the Insertion Sort only space complexity changes;
*. Imperative: O(1)
*. Recursive: O(n) because of the stacks that are created
The both imperative and the recursive versions are very similar, except in the recursive version, the comparison will start when the i is in second elements index which is 2
Code
The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms