Updated: Jun 3, 2022
Insertion sort is an in-place sorting algorithm. Insertion sort works by picking each unsorted element and placing it in its correct sorted position in the array. During its execution insertion sort divides the array into two portions, sorted portion and unsorted portion. Sorted elements will be on the left side of the array and unsorted elements will be on the right side. In each iteration one element is picked from unsorted portion and moved to its correct position in the sorted portion on the left.
For a given input array arr that needs to be sorted in ascending order, insertion sort does the following steps:
We assume that the first element is already sorted and start from the second element in the array.
We compare the second element to the element before it. If the current element is less than the element before it, we swap the two elements.
Next we move on to the third element and compare to all elements before it and swap if it is less than those elements.
We need to do the above steps for all the elements in the array.
To implement this algorithm we need to run two loops, an inner loop and an outer loop. Let i and j be the indexes of inner and outer loops respectively.
i points to the last sorted element in the sorted portion of the array. j points to the first unsorted element in the unsorted portion in the array.
To begin with we assume that the first element in the given array is sorted, so i points to the first element in the given array and j points to the second element.
We fix the outer loop and iterate through the inner loop. At the start of the inner loop we assign i to j, i.e j=i.
In each iteration of the inner loop check if arr[j] < arr[j-1]. As long as arr[j] < arr[j-1] we swap arr[j] and arr[j-1] decrement j. Else we break the inner loop and move on to the next iteration of the outer loop.
We repeat these steps until all the elements in the given array are processed.
Consider we are given the below input array: