JavaScript implementation of binary insertion sort.

README.md

JavaScript implementation of binary insertion sort

• Random list of ascending numbers generated in resultIndexList as seed list.
• Set of random numbers generated, insert position determined by insertAt() function.
• Each value inserted using resultIndexList.splice() to maintain sort order as progressing.

Reference

• https://en.wikipedia.org/wiki/Insertion_sort
• https://jeffreystedfast.blogspot.com.au/2007/02/binary-insertion-sort.html

script.js

'use strict';

function insertAt(item,sortedList,low = 0,high = (sortedList.length - 1)) {
	if (low == high) {
		// hit end of sortedList - done
		return (item > sortedList[low]) ? low + 1 : low;
	}

	// get midpoint of list and item value
	let mid = low + Math.floor((high - low) / 2),
		itemCompare = sortedList[mid];

	if (item > itemCompare) {
		// work higher end of list
		return insertAt(item,sortedList,mid + 1,high);
	}

	if (item < itemCompare) {
		// work lower end of list
		return insertAt(item,sortedList,low,mid);
	}

	// found equal value - done
	return mid;
}

// seed list of random ascending (sorted) numbers
let lastValue = 1,
	resultIndexList = [lastValue];

for (let i = 1;i < 10000;i++) {
	// generate random number at a higher value than last
	lastValue = Math.floor(Math.random() * 500) + lastValue;
	resultIndexList.push(lastValue);
}

// insert lots of values
let startTime = Date.now();

for (let i = 1;i < 1000;i++) {
	// generate random number and insert
	let nextValue = Math.floor(Math.random() * 2000000);

	resultIndexList.splice(
		insertAt(nextValue,resultIndexList),
		0,nextValue
	);
}

console.log(`Duration: ${(Date.now() - startTime)}ms`);

insertAt(4, [1,2,3]) and insertAt(2, [0,1,3]) both return 2, so there is some ambigiuity.

Hey @QuarkNerd - nicely spotted! Have corrected/fixed!