JavaScript Insertion Sort
Last week I wrote a blog about selection sort. Let’s continue on our sorting algorithm journey and discuss insertion sort. Conceptually I find insertion sort to be similar to selection sort. However, rather than finding the minimum in the unsorted section of the array, we will search through the already sorted elements at the beginning of the array to find out where to place each subsequent element. For example our first two elements are 3 and 1, we will swap them so they are in ascending order (1 followed by 3). After that if we had a 2, we would put it between the 1 and the 3. For this reason insertion sort is compared to the way you would sort playing cards in your hand.
Step by Step Example
Expected result
Sort in ascending order
Input: [4, 2, 5, 1, 3, 6]
Output: [1, 2, 3, 4, 5, 6]
First Iteration
We will actually be starting from the element at index 1. We will need to store that element in a variable to keep track of. Let’s call that variable current.
So, current = 2. From there we will check if the element before current is less than current. In this case 2 < 4, so we will look through the elements before current to figure out where we need to assign it.
The first step, is moving the number that is greater than current to the index ahead of it, temporarily we will have a duplicate number in our array, and we will not see current in the array. This is why we store its value into a variable to hold onto.
[4, 2, 5, 1, 3, 6] → [4, 4, 5, 1, 3, 6]
We have reached the beginning of our array, and so we know current is the lowest number in the sorted section of the array so far, and we will assign current to index 0.
[4, 4, 5, 1, 3, 6] → [2, 4, 5, 1, 3, 6]
Second Iteration
So we started at index 1, now current needs to be assigned to the next element, at index 2.
So current = 5. The number preceding current is 4.
4 < 5 so we will not need to do anything.
[2, 4, 5, 1, 3, 6] → [2, 4, 5, 1, 3, 6]
Third Iteration
current = 1 and since 1 < 5, we will need to figure out where to place 1.
move 5 up one index
[2, 4, 5, 1, 3, 6] → [2, 4, 5, 5, 3, 6]
current < 4, so move 4 up one index
[2, 4, 5, 5, 3, 6] → [2, 4, 4, 5, 3, 6]
current < 2, move 2 up
[2, 4, 4, 5, 3, 6] → [2, 2, 4, 5, 3, 6]
We have reached the beginning of the array, we know current is the smallest number so far, we will assign it to index 0.
[2, 2, 4, 5, 3, 6] → [1, 2, 4, 5, 3, 6]
Fourth Iteration
current = 3 3 < 5
[1, 2, 4, 5, 3, 6] → [1, 2, 4, 5, 5, 6]
current < 4
[1, 2, 4, 5, 5, 6] → [1, 2, 4, 4, 5, 6]
current > 2 so we will place it in the sorted section of our array
[1, 2, 4, 4, 5, 6] → [1, 2, 3, 4, 5, 6]
Final Iteration
current = 6 and 6 > 5, we don’t need to do anything
[1, 2, 3, 4, 5, 6] → [1, 2, 3, 4, 5, 6]
Now our array is sorted, and we’ve gone through each element of the array, so we are finished. Even if our array started out sorted, it would still need to step through each element of the array to check that current was greater than the element at the index before it.
Code
function insertionSort(arr){
for(let i = 1; i < arr.length; i++){
let current = arr[i];
let j = i - 1;
while(j >= 0 && arr[j] > current){
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}Explaining the Code
We start our for loop with i = 1 this is the same as it is in our step by step example. The reason is so we can start with the element at index 1. From there we assign our current variable, and then a variable j = i - 1, so we can begin our while loop by comparing current to the element before it.
The conditional of the while loop (j >= 0 && arr[j] > current) is so we will keep iterating backwards through the sorted section of the array until the element is no longer less than current, or until we are at the beginning of the array.
Each iteration through our while loop we are assigning the element after j to the value of j. This is like our behavior of moving the element. This is why we temporarily see duplicates in our array. From there we decrement j as we want to move backwards through the sorted section of the array towards index 0. We will break out of the while loop once the element at j index isn’t less than current or we have reached the beginning of the array.
Once we are out of the while loop, we still have the value of current which is missing from the array. current is no longer less than the value at j so we need to assign it to the element after j. This mimics the behavior of our step by step example, this would be where we assign current to the first duplicate value in the array.
Time and Space Complexity
Time Complexity
Similar to selection sort, the time complexity of insertion sort is n*(n-1)/2. This is because worst case, the array is in reverse order and the outer loop will have to run once for each element. Then the inner loop will first have to run to swap the first two elements, and then run one additional time for each consecutive element because the sorted section of the array will get 1 bigger with each iteration. However, unlike selection sort, if the elements are already in order the inner loop will not have to run at all. Also, the inner loop will run until it finds where the current element needs to be inserted into the array. That being said, worst case still simplifies to O(n²). Best case is O(n), because the first for loop will still run for each element in the array from index 1 onwards.
Space Complexity
Insertion sort sorts in place, giving it a space complexity of O(1).
Stable Sorting Algorithm
Unlike selection sort, insertion sort is a stable sorting algorithm. This means two elements with the same value will remain in the order that they appeared in the original array. Let’s walk through this with our student array that we used for selection sort.
We are taking an array of student objects that is alphabetically sorted, and sorting them by grade. The desired behavior is that the students will be sorted by grade, but also alphabetically within the grades. For example, all of the students in first grade will appear alphabetically followed by all of the students in second grade sorted alphabetically and so on.
let studentArr = [{name: “Al Cooper” , grade: 4}, {name: “Bobby Tables” , grade: 4}, {name: “Gracie Hopper” , grade: 3}]
Now let’s alter our insertion sort to handle these student objects:
function insertionSortStudentsByGrade(studentsArray){
for(let i = 1; i < studentsArray.length; i++){
let current = studentsArray[i];
let j = i - 1;
while(j >= 0 && studentsArray[j]['grade'] >
current['grade']){
studentsArray[j + 1] = studentsArray[j];
j--;
}
studentsArray[j + 1] = current;
}
return studentsArray;
}If you run studentArr through that function you will see that now it looks like this: [{name: “Gracie Hopper”, grade: 3}, {name: “Al Cooper”, grade: 4}, {name: “Bobby Tables”, grade: 4}]
Which is the desired behavior. Unlike selection sort, insertion sort has Al appear before Bobby. This is because the first loop of insertion sort will see that Al and Bobby are in the same grade, and then move on to Gracie. From there it will push Bobby into Gracie’s spot, and then Al into Bobby’s old spot, before placing Gracie at the front of the array. This way it preserves the order that the elements originally appeared.
In Conclusion…
While insertion sort still has O(n²) time complexity, you may be surprised to learn that is still has some use cases in the real world. Insertion sort is very fast on small lists, or in cases when the list is already almost sorted. So you may see other algorithms default to insertion sort if they are working with a small list size, or you may see it used when adding elements to an already sorted array.
