javascript - 为什么这个 1,000,000 的合并排序的实现要花这么长时间？

Question

我正在用 1,000,000 个数字对其进行测试，它只是有点悬。我以为它会轻而易举地突破 1,000,000。是我的实现吗？我有一种感觉，这是因为 slice()，有人知道吗？

编辑:刚收到这条消息: fatal error :CALL_AND_RETRY_2 分配失败 - 进程内存不足

TopDownSplitMerge(numbersArray);
function TopDownSplitMerge(arrayOfNumbers) {     
    var length = arrayOfNumbers.length
    var middleIndex = parseInt(length/2);

    if(length <= 1) {
        return arrayOfNumbers;
    }                       

    // Split left side
    var left = TopDownSplitMerge(arrayOfNumbers.slice(0, middleIndex));  

    // Split right side
    var right = TopDownSplitMerge(arrayOfNumbers.slice(middleIndex, length));   

    // Merge every back together
    return TopDownMerge(left, right);
}

function TopDownMerge(left, right) {
    var results = []

    while(left.length || right.length) {
        console.log("looping...");

        // Check if both sides are NOT empty, if so, then just finish shifting the non-empty side
        if(left.length && right.length) { 
            if(left[0] <= right[0]) {
               results.push(left.shift()) 
            } else {
               results.push(right.shift()) 
            }
        } else if(left.length) {
           results.push(left.shift()) 
        } else {
           results.push(right.shift()) 
        }

    }

    console.log("Merging....", results.length);
    return results;
}

Answer 1

有两件事我必须改变

var right = TopDownSplitMerge(arrayOfNumbers.slice(middleIndex, length));

....
....
....

function TopDownMerge(left, right) {
    var results = [], leftLen = left.length, rightLen = right.length;

    for (var i = 0, j = 0; i < leftLen || j < rightLen;) {
        if (i < leftLen && j < rightLen) {
            if(left[i] <= right[j]) {
                results.push(left[i]);
                i += 1;
            } else {
                results.push(right[j]);
                j += 1;
            }
        } else if (i < leftLen) {
            results.push(left[i]);
            i += 1;
        } else {
            results.push(right[j]);
            j += 1;
        }
    }
    return results;
}

编辑:现在我将其更改为接受索引而不是切片数组，这进一步提高了性能。

function TopDownSplitMerge(arrayOfNumbers, start, end) {
    var length = end - start;
    var middleIndex = start + parseInt(length / 2);

    if (length <= 1) {
        return [arrayOfNumbers[start]];
    }

    // Split left side
    var left = TopDownSplitMerge(arrayOfNumbers, start, middleIndex);

    // Split right side
    var right = TopDownSplitMerge(arrayOfNumbers, middleIndex, length);

    // Merge every back together
    return TopDownMerge(left, right);
}
TopDownSplitMerge(numbersArray, 0, numbersArray.length);

Jsperf:http://jsperf.com/so-q-19341534

jsperf 我的解决方案有 10,000,000 个数字:http://jsperf.com/solution-to-so-q-19341534