Insertion Sort

Mark as Completed

Lesson

Write a JavaScript function to implement the insertion sort algorithm that sorts an array of integers in ascending order. Explain your approach.

Background: The insertion sort algorithm is a simple sorting algorithm that works by picking an element and inserting it into its location before the elements that it is less than in order to get all of the numbers lined up in ascending order.

Example:

Input: [5, 2, 4, 6, 1, 3]
Output: [1, 2, 3, 4, 5, 6]

Walkthrough

Solution Code:

function insertionSort(array) {
  const length = array.length;
  for (let i = 1; i < length; i++) {
    const value = array[i];
    let previous = i - 1;
    while (previous >= 0 && array[previous] > value) {
      array[previous + 1] = array[previous];
      previous--;
    }
    array[previous + 1] = value;
  }
  return array;
}

Explanation:

We start by declaring a constant length
to store the length of the input array. Then, we loop through each element starting from the second element (index 1) by declaring a variable i
and setting it to 1.For each element, we store the value of the element in a constant value
and store the previous index in a variable previous
, which is initialized to i - 1
. We then enter a while loop that continues as long as previous
is greater than or equal to 0 and the element at previous
is greater than value
. Inside the while loop, we move the element at previous
to the right by setting the element at previous + 1
to the element at previous
. We then decrement previous
to check the previous element.Once we exit the while loop, we insert the value by setting the element at previous + 1
to value
. We repeat this process for each element in the input array, and then return the sorted array.

Big O Complexity Analysis: The time complexity of the insertion sort algorithm is O(n^2), where n is the number of elements in the array. This is because the algorithm involves nested loops. The outer loop iterates over each element in the array, and the inner loop may iterate over every previous element, resulting in a worst-case time complexity of O(n^2). The space complexity of the algorithm is O(1), since the algorithm sorts the array in place without creating any new arrays.

Previous Lesson Next Lesson