了解就地合并排序

Question

我很难理解合并排序的就地版本。

function merge(left, right){
    var result  = [],
        il      = 0,
        ir      = 0;

    while (il < left.length &#038;&#038; ir < right.length){
        if (left[il] < right[ir]){
            result.push(left[il++]);
        } else {
            result.push(right[ir++]);
        }
    }

    return result.concat(left.slice(il)).concat(right.slice(ir));
}


function mergeSort(items){

    if (items.length < 2) {
        return items;
    }

    var middle = Math.floor(items.length / 2),
        left    = items.slice(0, middle),
        right   = items.slice(middle),
        params = merge(mergeSort(left), mergeSort(right));

    params.unshift(0, items.length);
    items.splice.apply(items, params);
    return items;
}

params前面加0和items.length有什么用？我不明白 items.splice.apply 在做什么，但从控制台记录的一些示例来看，它似乎只是删除了未转移到 params 的内容。这是什么原因？

Answer 1

TLDR：它将 items 的内容替换为排序后的版本。

Array.prototype.splice 有 the following signature:

array.splice(start, deleteCount[, item1[, item2[, ...]]])

它删除从索引 start 开始的 deleteCount 项，并用提供的项替换它们。

items.splice.apply(items, params) 使用取自 params 的参数执行 items.splice(...)。 params.unshift(0, items.length)之后，params是

[0, items.length, sortedItem1, sortedItem2, ...]

以便调用执行 items.splice(0, items.length, sortedItem1, sortedItem2, ...)，删除从索引 0 开始的 items.length 个项目（因此所有项目）并用排序的项目替换它们。

了解就地合并排序

Understanding in-place mergesort

javascript

mergesort