Insertion Sort Algorithm Implementation in JavaScript

Use Case:

The Insertion Sorting algorithm is a program that runs one loop through a dataset and upon coming to a value, it checks for values in the dataset prior to the current value that are larger than the current value. Then, if there are larger values, it moves the current value forward to its ordered place and shifts all other values back.

Here's a description from Wikipedia:

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time and provides advantages [such as] simple implementation, efficiency for small data sets, stability, and space-efficient.

Hey, Tyler here. I'm currently working on some great web development and digital marketing products and services over at ZeroToDigital.

If that sounds interesting to you, please check it out!

Below is an implementation of the Insertion Sort algorithm in JavaScript.

JavaScript

insertionSort = (array) => { // O(n^2)
	if (array.length <= 1) return array
	for (var i = 0; i < array.length; i++) {
		let temp = array[i], j = i - 1
		while (j >= 0 && array[j] > temp) {
			array[j + 1] = array[j]
			j--
		}
		array[j + 1] = temp
	}
	return array
}

The insertionSort function takes an array of the dataset and returns the sorted array. First, it'll check to be sure we're dealing with a dataset of more than 1, then it'll loop through the array.

At the beginning of each loop, the temp variable will be set equal to the value at the current array index and j will equal the current index minus 1.

Then we'll run a loop for all values prior to the current value in the dataset. If we find a value that is larger, we'll shift that value backwards and deduct j by 1. Once we've reached the beginning of our dataset, we'll place our current value at the location of the last-found larger value and then continue looping through the dataset forward.

Results

JavaScript

var array = [8,3,5,9,1,5,9,2,3,8,4]
insertionSort(array)
// 8,3,5,9,1,5,9,2,3,8,4
// 3,8,5,9,1,5,9,2,3,8,4
// 3,5,8,9,1,5,9,2,3,8,4
// 3,5,8,9,1,5,9,2,3,8,4
// 1,3,5,8,9,5,9,2,3,8,4
// 1,3,5,5,8,9,9,2,3,8,4
// 1,3,5,5,8,9,9,2,3,8,4
// 1,2,3,5,5,8,9,9,3,8,4
// 1,2,3,3,5,5,8,9,9,8,4
// 1,2,3,3,5,5,8,8,9,9,4
// 1,2,3,3,4,5,5,8,8,9,9

Insertion Sort isn't a great algorithm for large datasets as its time complexity is equal to O(n^2) but, as Wikipedia noted, it is a stable sorting algorithm and only requires a space complexity of O(1).

Check out other sorting algorithm implementations in JavaScript: