Implement Insertion Sort in JavaScript

Algorithms
September 29, 2016

This article is part of a series covering sort algorithms in JavaScript. You can find the rest of the series here. If you’re new to sorting algorithms, or algorithms in general, read this first to get a solid foundation for moving forward. 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; };

Next up? Merge sort. One of the most widely used sorting algorithms in browsers today.

Having worked across sites raking in over 50 billion website visits annually, Michael Mitrakos can help your business to crush the web game with an award winning website.

I also created Wanderlust Extension to discover the most beautiful places across the world with highly curated content. Check it out!

More Blog Posts