In this sorting technique, a region of the array, which might be the lower or upper part, is considered as sorted. An element outside the sorted region is picked up and its appropriate place is searched for in the sorted region (so that even after the insertion of this element, the region remains sorted) and the element is inserted there, hence the name insertion sort.
We will create a function for insertion sort called InsertionSort, which we will invoke as follows, where arr is the array to be sorted and consists of n number of elements.
Here are the steps that are followed in the InsertionSort method:
- Initialize a variable, say i, to 1.
- Repeat steps...