**Insertion sort** is another commonly used sorting algorithm. Like bubble sort, it is also simple and easy to implement. In insertion sort, the comparison starts by comparing the second element of the array with the first element. They are swapped accordingly. Then, the rest of the array is iterated. If the next element is larger than the current element, they are swapped. Then, the swapped element is compared with the already sorted portion of the array and if required, the element is inserted at the correct position.

Let’s understand with the help of an example.

`[8, 2, 1, 3, 9]`

-> The sorting starts by comparing the second element, i.e. 2 with the first element, i.e. 8.`[2, 8, 1, 3, 9]`

-> Since 8 > 2, they are swapped. Next, 8 is compared with the next element, i.e. 1.`[2, 1, 8, 3, 9]`

-> 8 > 1, they are swapped. Next, 1 is compared with the sorted portion (left side of the element).`[1, 2, 8, 3, 9]`

-> Since 2 > 1, they are swapped. Next, 8 is compared with 3.`[1, 2, 3, 8, 9]`

-> 8 > 3, they are swaped. Now, 3 is compared with the sorted portion.`[1, 2, 3, 8, 9]`

-> As they are already in the order, no swapping is performed.`[1, 2, 3, 8, 9]`

-> Next, 8 is compared with 9. As 8 < 9, no swapping is performed.

The following is the implementation of insertion sort using JavaScript.

let arr = [8, 2, 1, 3, 9] let l = arr.length; for (let i = 1; i < l; i++) { // first element of the unsorted array, starting from the second element let current = arr[i]; // last element of the sorted portion, starting from the first element let j = i-1; while ((j > -1) && (current < arr[j])) { arr[j+1] = arr[j]; j--; } arr[j+1] = current; } console.log(arr) // [1, 2, 3, 8, 9]

The time complexity of insertion sort is O(n^2) while the space complexity is O(1).

Previous Article

javascript algorithms - Bubble sort Explained using Javascript .javascript algorithms - Bubble sort Explained using Javascript .

January 10, 2021

1 min

Big O notation In Javascript

January 07, 2021

3 min

forEach() Method in javascript and how to use it .

January 04, 2021

1 min

Functional programming in javascript

December 06, 2020

2 min

Closures in Javascript for beginners

December 01, 2020

3 min

Quick Links

Legal Stuff