Insertion sort algorithm is very helpful in those cases where we have a smaller number of elements in a list or where most of the list is already sorted and fewer elements are misplaced.
How Insertion Sort Works
Let’s consider an example to better understand the logic behind the insertion sort. Suppose we have an unsorted array of 6 elements and we have to sort them using insertion sort:
Now to sort the above array, we will iterate the array from index 1 to the last index. Initially, we assume the 0th index of the array is sorted, thereafter we will make a comparison of the current element with its prior element. If the current element is less than the prior element then we will swap their positions.
In the first step, we will compare index 1 with index 0, the value of the first index ‘47’ is greater than 0th index value, so there will be no change in the first step (elements wouldn’t swap):
Now, in the second step, we will assume that the first two elements are sorted, so cursor will be at index 2, and we will compare index 2 with its prior elements:
Since ‘25’ is smaller than ‘47’, swap ‘25’ and ‘47’. Next, ‘25’ is also compared with the 0th index value. ‘25’ is greater than ‘15’ so it wouldn’t be swapped.
The array after the second step will be updated as:
Here in the third step, we consider the first three values are sorted and the cursor will be at the third index. So, we will compare the third index with its prior values:
At index 3, ‘55’ is compared with each element one by one but it is greater than all of its prior elements so there will be no change in the position of array elements.
Now we are at index 4, where we have a value ‘20’ and we have to compare it with all the prior elements of the array:
Since ‘20’ is less than ‘25’, ‘47’ and ‘55’ so it will be inserted at the first index, and ‘25’, ‘47’ and ‘55’ will be moved to the right side by one index (i+1 index) from their current indexes.
The updated array will be:
Now we are at index 5 where the current value is ‘10’ which is the smallest among all the array values, so it will be inserted at the 0th index.
In this way, the whole array will be sorted using insertion sort:
let i, pivot_value, j;
for (i = 1; i = 0 && input_array[j] > pivot_value)
input_array[j + 1] = input_array[j];
j = j - 1;
input_array[j + 1] = pivot_value;
let input_array = [15,47,25,55,20,10 ];
let array_length = input_array.length;
console.log("final sorted array : ", input_array);
In the above code, we created a function “insertion_sort” and passed it the input array and array length. Then we iterated the loop until the length of the array.
Inside the loop, we selected the ‘pivot_value = input_array[i]’ as a pivot value to make a comparison of the current element with its prior elements and set “j= i-1” which represents the last element of our sorted array.
Here in each iteration, the current element is assigned to the pivot value and the pivot value will be considered as the first element of the unsorted array in each step.
We utilize a while loop to sort array elements, here in this loop we compare the current element with its prior elements. If the current element is less than any of the prior elements, and we found the appropriate position to insert that element in the sorted array then we insert that element at the appropriate position and move the other elements one place to the right side. And the whole phenomenon is repeated for each step until the array is sorted completely.
Finally, we call the “insertion_sort” function and print the sorted array at the console of the browser using the “console.log” method. The output of the insertion sort algorithm will be:
Insertion sort is a sorting algorithm that sorts one element at a time. It inserts the element at the appropriate position one by one to create one sorted array. It provides efficient results if the number of array elements is small and most of the array elements are already sorted.