What is Insertion Sort and How to Implement it in JavaScript

Insertion sort is another common sorting algorithm. It sorts elements by repeatedly comparing them to their neighbor on the left and swapping if the left hand element is larger than the current element. It begins on the left hand side or 0 index of an array and advances one element at a time. A real life example would be sorting a hand of cards where the player moves each card to its proper place one card at a time.

Insertion sort has a variable time complexity ranging. In the worst case it is O(n*2) if the list is in reverse order and every element requires sorting. In the bes case it is O(n) if the list is already sorted.

Step-by-step Example

Starting array: [3, 1, 10, 9, 4, 7]

Fist Pass

Index to be sorted = 0.

[3, 1, 10, 9, 4, 7] => [3, 1, 10, 9, 4, 7]

There is no change as the element in index 0 does not hand a neighbor on the left hand side.

Second Pass

Index to be sorted = 1.

[3, 1, 10, 9, 4, 7] => [1, 3, 10, 9, 4, 7]

1 < 3 so the two element are swapped. There are no more neighbors to compare with after that so the sorting algorithm moves on to the next element.

Third Pass

Index to be sorted = 2.

[1, 3, 10, 9, 4, 7] => [1, 3, 10, 9, 4, 7]

No change as the selected element is greater than its neighbor.

Forth Pass

Index to be sorted = 3.

[1, 3, 10, 9, 4, 7] => [1, 3, 9, 10, 4, 7]

9 < 10 so they are swapped. 9 > 3 so no further swaps are made.

Fifth Pass

Index to be sorted = 4.

[1, 3, 9, 10, 4, 7] => [1, 3, 4, 9, 10, 7]

4 < 10 so they are swapped. 4 < 9 so they are swapped. 4 > 3 so no further swaps are made.

Sixth Pass

Index to be sorted = 5.

[1, 3, 4, 9, 10, 7] => [1, 3, 4, 7, 9, 10]

7 < 10 so they are swapped. 7 < 9 so they are swapped. 7 > 4 so no further swaps are made. This was the last index of the array so the algorithm is finished sorting.

JavaScript Implementation of Insertion Sort

1const startingArray = [3, 1, 10, 9, 4, 7]
2
3function insertionSort(arr) {
4  // loop through the array
5  for (let i = 1; i < arr.length; i++) {
6    // current element
7    let current = arr[i]
8
9    let neighborIndex = i - 1
10
11    // move current element to its proper place
12    while (current < arr[neighborIndex] && neighborIndex >= 0) {
13      // advance neighbor one place to the right
14      arr[neighborIndex + 1] = arr[neighborIndex]
15
16      // lower the index so the while loop can fire again, if needed
17      neighborIndex -= 1
18    }
19    // assign the current element to new location
20    arr[neighborIndex + 1] = current
21  }
22  return arr
23}
24
25insertionSort(startingArray)

Insertion sort is most useful when either the number of elements is small, or the input array is almost sorted.

Cheers!

Find a mistake? Help me fix it by submitting a pull request.