This post covers the essentials of insertion sort using JavaScript. We will use a simple array to demonstrate the concepts of Insertion Sort before getting into code.
Concept:
In insertion sort, we divide the initial unsorted array into two parts; sorted part and unsorted part. Initially the sorted part just has one element (Array of only 1 element is a sorted array). We then pick up element one by one from unsorted part; insert into the sorted part at the correct position and expand sorted part one element at a time.
Let’s see this using illustration below:
Step 1: Initial Array

Step 2:

Number 5 is in sorted part of the array. We need to pick up the first number in unsorted part, i.e 3, and insert it into the sorted part at correct position. We make a copy of number 3 and compare this copy with the numbers in the sorted part starting at the last element in the sorted part, in this case, 5.
Step 3:

Since 5 > 3, we expand the sorted part by replacing number 3 in the unsorted part by 5. Next, we insert the number 3 (using the copy we stored earlier) at the previous position of 5. Now, the sorted part has expanded to 2 elements while unsorted part is reduced to 3 elements.
Step 4:

We pick the next number in the unsorted part, number 1. Again, we make a copy of this number and compare it with numbers in sorted part one by one.
Step 5:

Since 5 > 1, we expand the sorted part by replacing number 1 in the unsorted part by 5. We compare the copy of number 1 with the next element in sorted array, 3.
Step 6:

Since 3 > 1, we need to shift 3 to next position in the sorted part. We replace the number 5 at the second position with number 3. Since there are no more numbers, we insert copy of number 1 at 1st position.
Step 7:

Repeating the same process with number 2, we expand the sorted part and shift numbers 3 and 5:


Step 8:

Next, we compare number 2 with number 1. This time, 1 < 2. So, we need to insert the number 2 after number 1. We replace the number 3 at the second position with number 2.

Step 9:
Similarly:

Complexity:
Best CaseAverageWorst CaseO(n)O(n²)O(n²)## Insertion Sort in Javascript
Implementation of Insertion Sort:
function insertionSort(unsortedList) {
var len = unsortedList.length;
for (var i = 1; i < len; i++) {
var tmp = unsortedList[i]; //Copy of the current element.
/*Check through the sorted part and compare with the number in tmp. If large, shift the number*/
for (var j = i - 1; j >= 0 && (unsortedList[j] > tmp); j--) {
//Shift the number
unsortedList[j + 1] = unsortedList[j];
}
//Insert the copied number at the correct position
//in sorted part.
unsortedList[j + 1] = tmp;
}
}
var ul = [5, 3, 1, 2, 4];
insertionSort(ul);
console.log(ul);
Practice Exercise:
- Write a program in JavaScript to sort following list in ascending order using Insertion Sort Algorithm.var nums = [34, 23, 12, 45, 9, 1, 24];
- Sort the list present in Q1 in descending order.
- Sort the following array of Persons in ascending order of ‘age’ using Insertion Sort.var persons = [{"name": "john","age": "23"},{"name": "harry","age": "21"},{"name": "jack","age": "25"}];