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:

1. 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];
2. Sort the list present in Q1 in descending order.
3. 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"}];