What is Insertion Sort
Insertion sort is a simple sorting algorithm that sorts the elements one at a time. It is more efficient in practice when compared with other simple quadratic algorithms like bubble sort or selection sort. It can even outperforms more advanced algorithms like quick sort or merge sort on a small list.
Steps to Sort using Insertion Sort
Implementing Insertion Sort just needs just 2 basic loops.
- Start a loop from the left side of the array, checking each elements to sort them in place.
- Then do a second loop against all the elements on the left to insert the element in the correct location.
That’s it, easy and simple.
Before we start, we need to note that Insertion Sort is an destructive function, as it will modify the array you put into it. If you don’t want to modify the original array, make sure to use the spread operator to create a new variable before injecting this sorting algorithm.
We now start by creating a for loop to go through all the elements in the array to check them against the left side to inject it in the correct location.
Then we want to compare it with all the elements on the left of the key until we find an element that is smaller than our key or until we reach the beginning of the array.
While we are comparing the key with every element, if the element isn’t smaller than the key, we want to shift it one step to the right, to give room for the key to insert into the correct location.
And lastly we just need to insert the key into the correct location