How to implement insertion sort using JavaScript (with code example)

The insertion sort algorithm is a sorting algorithm that allows you to sort an array by inspecting the elements from left to right and placing larger elements to the right of the smaller elements.

The insertion sort algorithm starts by comparing your element at index 0 and index 1. When the element at index 1 is smaller than index 0, then the element at index 0 will be moved to the right. Suppose you have the following array elements:

let arr = [5, 3, 6, 1, 4];

The first iteration of the insertion sort will compare the numbers 5 and 3. Since 3 is smaller than 5, then 5 is moved to the right and 3 is inserted to index 0:

let arr = [3, 5, 6, 1, 4];
// first insertion sort iteration finished

Once the first iteration is finished, insertion sort will next compare between 6 and 5. The number 5 won’t be moved because 6 is larger than 5, and the second iteration will skip moving elements:

let arr = [3, 5, 6, 1, 4];
// second insertion sort iteration finished

Next, the number 1 will be compared to 6, and the number 6 will be moved to the right because it’s larger than 1. The number 5 will also be moved to the right because it’s larger than 1. The same happens with number 3:

let arr = [1, 3, 5, 6, 4];
// third insertion sort iteration finished

Finally, you have the last element number 4 compared to the rest of the elements. The numbers 5 and 6 will be moved to the right because they are larger than 4, then 3 won’t be moved to the right since it’s smaller than 4.

The number 4 will take its place between 3 and 5. Since all elements have been sorted, the insertion sort will stop its execution and return the sorted array:

let arr = [1, 3, 4, 5, 6];

Now that you have the general idea of how insertion sort works, let’s see how you can implement one using JavaScript.

Implementing insertion sort using JavaScript

To implement the insertion sort in JavaScript, you need to first create a function that accepts an array arr as its parameter. Because the insertion sort is done in-place, the arr variable will be returned at the end of function execution:

function insertionSort(arr) {
  return arr;
}

Then, you need to loop over the array and start comparing the elements at index 0 and 1. You can use a [for loop] https://sebhastian.com/javascript-for-loop/ ) that iterates through the array length follows:

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    // First, choose the element at index 1
    let current = arr[i];
  }
  return arr;
}

You need to initialize the for counter with 1 instead of 0 so that the first iteration will compare correctly. Next, create another for loop that iterates through the arr backward from right to left, starting from the element on the left side of arr[i] element (arr[i - 1]):

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    // First, choose the element at index 1
    let current = arr[i];
    let j;

    // Loop from right to left, starting from i-1 to index 0
    for (j = i - 1; j >= 0 && arr[j] > current; j--) {
      // as long as arr[j] is bigger than current
      // move arr[j] to the right at arr[j + 1]
      arr[j + 1] = arr[j];
    }
  }
  return arr;
}

You may notice that the j variable is oddly initialized outside of the second for loop. This is required because after all the elements have been moved, you want to insert the current element right next to the arr[j] element.

For example, you need to know where the j index to place the element 4 between 3 and 5 as in the following array:

let arr = [3, 5, 4];

First, 5 will be moved to right, then the second for loop stops running because 3 is smaller than 4.

let current = 4;
let arr = [3, 5, 5];

Right at that moment, you want to insert 4 next to 3, so you assign the current variable to arr[j + 1] after the loop:

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    // First, choose the element at index 1
    let current = arr[i];
    let j;

    // Loop from right to left, starting from i-1 to index 0
    for (j = i - 1; j >= 0 && arr[j] > current; j--) {
      // as long as arr[j] is bigger than current
      // move arr[j] to the right at arr[j + 1]
      arr[j + 1] = arr[j];
    }
    // Place the current element at index 0
    // or next to the smaller element
    arr[j + 1] = current;
  }
  return arr;
}

And with that, your JavaScript insertion sort algorithm is finished. You can test the function by calling several different arrays:

console.log(insertionSort([5, 3, 6, 1, 4])); // [1, 3, 4, 5, 6]
console.log(insertionSort([11, 15, 12, 10, -2])); // [-2, 10, 11, 12, 15]

Next, let’s learn about the performance of insertion sort measured in Big O Notation

Insertion sort Big O measurement

The insertion sort is best suited for small arrays because the double for loop inside insertion sort means that the algorithm runs in O(n²) or quadratic time complexity at its worst-case scenario, because each element needs to be compared to all elements on the left side of it.

This means if sorting an array with the size of 2 requires 4ms, sorting an array with the size of 20 requires 400ms. Any algorithm with quadratic time complexity scales poorly.

On the other hand, the insertion sort is a stable algorithm because its in-place sorting and O(1) space complexity will conserve your memory use. The insertion sort is also adaptive because it will stop running once an element is found to be smaller than the current value under sort.

There is no rule about when to use insertion sort, but it’s not recommended to use the algorithm for large datasets (bigger than 100,000).