js: merge sort

mergesort.js

function mergesort(list) {
	if(list.length <= 1) return list;
	var l = mergesort(list.slice(0, list.length / 2));
	var r = mergesort(list.slice(list.length / 2));
	return merge(l, r);
}

function merge(l, r) {
	var result = [];
	while(l.length > 0 || r.length > 0) {
		if(l.length > 0 && r.length > 0) {
			if(l[0] <= r[0]) {
				result.push(l.shift());
			} else {
				result.push(r.shift());
			}
		}
		else if(l.length > 0) result.push(l.shift());
		else if(r.length > 0) result.push(r.shift());			
	}
	return result;
}

mergesort([4, 2, 3, 1]); // [1, 2, 3, 4]
mergesort([5, 1, 3, 4, 2]); // [1, 2, 3, 4, 5]