Merge sort implementation in JavaScript.

merge_sort.js

function merge(xs, leftStart, leftEnd, rightStart, rightEnd) {
    var i = leftStart;
    var j = rightStart;
    var merged = [];
    var currentLeft, currentRight;

    // Merge.
    while (i <= leftEnd || j <= rightEnd) {
        currentLeft = xs[i];
        currentRight = xs[j];
        if ((currentLeft <= currentRight || j > rightEnd) && i <= leftEnd) {
            merged.push(currentLeft);
            i++;
        } else if ((currentLeft > currentRight || i > leftEnd) && j <= rightEnd) {
            merged.push(currentRight);
            j++;
        }
    }

    var k;

    // Update source array.
    for (k = 0; k <= rightEnd - leftStart; k++) {
        xs[k + leftStart] = merged[k];
    }
}

function mergeSort0(xs, start, end) {
    var middle = Math.ceil((end - start) / 2);
    var leftStart = start;
    var leftEnd = Math.max(start, middle - 1);
    var rightEnd = end;
    var rightStart = Math.min(rightEnd, leftEnd + 1);

    if (leftStart !== rightEnd) {
        mergeSort0(xs, leftStart, leftEnd);
        mergeSort0(xs, rightStart, rightEnd);
        merge(xs, leftStart, leftEnd, rightStart, rightEnd);
    }

    return(xs);
}

function mergeSort(xs) {
    if (xs.length <= 1) {
        return(xs);
    }

    return(mergeSort0(xs, 0, xs.length - 1));
}