Implement Insertion Sort in JavaScript

Implement Insertion Sort in JavaScript

This article is part of a series covering sort algorithms in JavaScript. Today I’ll be covering the ins and outs of insertion sort. Insertion sort is more complex but a little more useful than bubble sort. The worst case scenario for it is similar to bubble sort’s but its best case makes it suited for times when you’re pretty sure a list almost sorted or likely already sorted. Let’s get the big picture.

Insertion sort works by looking at each element within a list (starting with the second element) and comparing it with the item before. If the item before is larger, they are swapped. This continues until the item is smaller at which point we do the same for the next element in the list.


Benefits

Insertion sort isn’t all that bad.. as long as you use it in the right circumstances.

  • It’s faster than most O(n log n) sorting algorithms for small lists.
  • It’s extremely memory efficient requiring only O(1) auxiliary space for the single item that is being moved.
  • It’s stable — equal elements appear in the same order in the sorted list.
  • It’s adaptive — it’s fast when sorting mostly sorted lists or when adding items to an already sorted list.
  • It’s very easy to implement!

Complexity

The time complexity of this algorithm, at worst case, is quadratic — O(n²). As n approaches infinity the average case approaches the worst case divided by two. However since if your list is sorted or nearly so, it can be O(n) in a best case scenario and thus well adapted to that scenario.

When it's fast

As mentioned above it can be fast under certain circumstances. Consider the array [6, 7, 8, 9, 5 ], when using an algorithm like merge sort we would still need to split all the items and then merge them back up. With insertion sort we just need to verify that [6, 7, 8, 9] are in the correct ‘sorted so far’ order, then we shift all of them up one index for 1.

Because insertion sort is an adaptive sort, it also makes it an ‘online algorithm’, which means we can start sorting before we get all the items and then merge the lists once the partial sorting has completed.

Pseudocode

function insertionSort(array) 
  Loop through array
    Create temp var for current element
    Create var and set equal to previous element's index
    Loop backwards while index >= 0 and current element > temp var
      Set next element equal to current element
    Set next element equal to temp

Code

const insertionSort = (array) => {
    const length = array.length;

    for (let i = 1; i < length; i++) {
        let key = array[i];
        let j = i - 1;
        while (j >= 0 && array[j] > key) {
            array[j + 1] = array[j];
            j = j - 1;
        }
        array[j+1] = key;
    }
    return array;
};