In insertion sort, we logically divide the array into two parts.
- Sorted part
- Unsorted part
We will start with one element in the sorted part which is the first index and all other elements in the unsorted part.
In every step we will insert the first element of the unsorted part to the sorted part.
We will assign the first element of the unsorted part to a variable value.
Then, compare the value with the elements in the sorted part(from the last element). If the value is smaller than the element of the sorted part (or we reach index 0). Insert the value in place of the element.
Every time we add the first element of an unsorted part to the sorted part the length of the sorted array grows by one.
Let’s sort the array using insertion sort.
First Step
Value = 36
36 > 22
So, 36 is in its correct position, and we will insert 36, in its current position.
Second Step
Value = -18
-18 < 36
so we must insert -18 before 36, so to make room for -18, we will shift 36 to its position + 1.
-18 < 22
Shift 22 to position + 1.
Now, as there are no more elements in the sorted array to compare with, assign -18 to index 0.
Third Step
Value = 6
6 < 36
Shift 36 to right
6 < 22
shift 22 to right
6 > -18, insert 6 at index 1
Fourth Step
Value = 62
62 > 36
So, 62 is in its correct position, and we will insert 62, in its current position.