Merge Sort

gistfile1.js

function merge_sort(a_array) { 
    if (a_array.length < 2) {
	return a_array;
    }
    var mid = parseInt(a_array.length / 2); 
    var left = a_array.slice(0, mid); 
    var right = a_array.slice(mid, a_array.length);

    return merge(merge_sort(left), merge_sort(right));
}

function merge(left, right) { 
    var merged = new Array []; 
    
    while (left.length && right.length) {
	if (left[0] <= right[0]) { 
	merged.push(left.shift());
	} else {
	    merged.push(right.shift()); 
	}
    }
    while (left.length) {
	merged.push(left.shift());
    }
    while (right.length) {
	merged.push(right.shift());
    }
    return merged;
}
    
merge_sort(3, 5, 7, 2, 9, 1);