Asynchronous bottom-up merge sort in JavaScript

gistfile1.js

var AsyncComparator = function(list) {
	this.listsAtCurrentLevel = [];
	this.listsAtNextLevel = [];
	this.listMerged = [];
	for(var i=0; i<list.length; i++) {
		this.listsAtCurrentLevel[i] = [list[i]];
	}
};

AsyncComparator.prototype.getA = function() {
	return this.listsAtCurrentLevel[0][0];
};

AsyncComparator.prototype.getB = function() {
	return this.listsAtCurrentLevel[1][0];
};

AsyncComparator.prototype.compared = function(compareValue) {
	// Add current images to this.listMerged
	if(compareValue > 0) {
		this.listMerged.push(this.listsAtCurrentLevel[1].shift());
	} else {
		this.listMerged.push(this.listsAtCurrentLevel[0].shift());
	}
	
	if(!this.listsAtCurrentLevel[0].length || !this.listsAtCurrentLevel[1].length) {
		// We have merged the current A and B
		
		// Put merged list onto list of merged lists at next level
		this.listsAtNextLevel.push(this.listMerged.concat(this.listsAtCurrentLevel[0])
			.concat(this.listsAtCurrentLevel[1]));
		this.listsAtCurrentLevel.splice(0, 2);
		this.listMerged = [];
		
		// Check if we have should move to next level
		if(this.listsAtCurrentLevel.length < 2) {
			// If there is one list at the current merge level, move it to the next
			if(this.listsAtCurrentLevel.length) {
				this.listsAtNextLevel.push(this.listsAtCurrentLevel[0]);
			}
			
			// Move lists at next merge level to current level
			this.listsAtCurrentLevel = this.listsAtNextLevel;
			this.listsAtNextLevel = [];
		}
		
		// Check if we're done
		if(this.listsAtCurrentLevel.length == 1) return false;
	
		// Sort lists by list length
		// See http://www.cosc.canterbury.ac.nz/research/reports/TechReps/1997/tr_9701.pdf
		// Ideally we could do this more efficiently, but we don't really care about the
		// computational complexity here except with respect to the comparison call
		this.listsAtCurrentLevel.sort(function(a, b) { return a.length - b.length; });
	}
	
	return true;
};

AsyncComparator.prototype.getSorted = function() {
	if(this.listsAtCurrentLevel.length !== 1 || this.listsAtNextLevel.length !== 0) {
		throw "Not yet sorted";
	}
	return this.listsAtCurrentLevel[0];
};

function test() {
	const TEST_ARRAY_SIZE = 100;
	
	var arr = [];
	for(var i=0; i<TEST_ARRAY_SIZE; i++) {
		arr[i] = Math.random();
	}
	var comparator = new AsyncComparator(arr), a, b;
	var i1 = 0;
	var compareCache = {};
	do {
		a = comparator.getA();
		b = comparator.getB();
		i1++;
	} while(comparator.compared(a - b));
	var sorted = comparator.getSorted();
	
	var i2 = 0;
	arr.sort(function(a, b) {
		i2++;
		return a - b;
	});
	
	for(var i=0; i<TEST_ARRAY_SIZE; i++) {
		if(sorted[0] !== arr[0]) {
			alert("Test failed");
		}
	}
	alert("Test succeeded ("+i1+" comparisons versus "+i2+" for built-in sort)");
}
test();