MergeSort

by mmarcon

JavaScript

Math.arbitraryRandom = function(min, max) {
    return Math.floor(Math.random() * (max - min) + min);
}
var toBeSorted = [], i;

for (i = 0; i < 10000; i++) {
    toBeSorted.push (Math.arbitraryRandom (0, 10000));
}

document.write ('[' + toBeSorted.join() + ']');

function mergeSort (array) {
    var left, right, l, result;
    if (array.length <= 1) {
        return array;
    }
    else {
        l = Math.floor(array.length / 2);
        left = array.slice(0, l);
        right = array.slice(l);
        left = mergeSort(left);
        right = mergeSort(right);
        result = merge(left, right);
        return result;
    }
}

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

toBeSorted = mergeSort (toBeSorted);
document.write ('<br/>[' + toBeSorted.join() + ']');