Javascript insort function

I recently had the need for some sorted insertion in Javascript arrays, thought I'd share this tiny bit of code:

Array.prototype.bisect = function(x, lo, hi) {
var mid;
if(typeof(lo) == 'undefined') lo = 0;
if(typeof(hi) == 'undefined') hi = this.length;
while(lo < hi) {
mid = Math.floor((lo + hi) / 2);
if(x < this[mid]) hi = mid;
else lo = mid + 1;
return lo

Array.prototype.insort = function(x) {
this.splice(this.bisect(x), 0, x);

Of course, these methods only work on an already sorted (or empty) array, so if you're using them on an array that came from elsewhere, sort it first. But once sorted, these insertions will maintain the sortedness, no need to 'push' and 'sort' every time you need to insert something into a sorted array.

(lo and hi parameters are optionally possible for the bisection method to allow restricted searches)


Popular posts from this blog

Procedural music with PyAudio and NumPy