javascript - javascript中归并排序的简单实现

Question

以下合并排序算法的实现有什么问题。它只是返回未定义。

我怀疑错误出在合并函数中。

有人可以帮我指出错误吗？

    function mergeSort(arr1, lower, higher) {

    if (lower < higher) {
        var mid = Math.floor((lower + higher) / 2);
        mergeSort(arr1, lower, mid);
        mergeSort(arr1, mid + 1, higher);
        merge(arr1, lower, mid, higher);
    }
}

以及合并功能

function merge(arr1, lower, mid, higher) {

    var i = lower;
    var j = mid + 1;
    var k = 0;
    var mergearr = [];

    while (i < j && j <= higher) {

        if (arr1[i] <= arr1[j]) {
            mergearr[k] = arr1[i];
            k++;
            i++;
        } else {
            mergearr[k] = arr1[j];
            k++;
            j++;
        }

    }

    if (i === j) {
        while (j < higher) {
            mergearr[k] = arr1[j];
            k++;
            j++;
        }
    } else if (j > higher) {
        while (i < j) {
            mergearr[k] = arr1[i];
            k++;
            i++;
        }
    }


    for (var a = 0; a <= k; a++) {
        console.log(a);
        arr1[a] = mergearr[a];
        console.log(arr1[a]);
    }

    return arr1;
}

这是控制台上的输出

index: 0
 value: 4
index: 1
 value: 5
index: 2
 value: 4
index: 3
 value: undefined
index: 0
 value: 4
index: 1
 value: 4
index: 2
 value: 5
index: 3
 value: 4
index: 4
 value: undefined
index: 0
 value: undefined
index: 1
 value: 4
index: 2
 value: undefined
index: 3
 value: undefined
index: 0

Answer 1

抛开排序中可能出现的“off-by-1”错误不谈，merge() 函数在将合并列表复制回源数组的方式上存在问题。该函数被告知从 lower 合并到 higher，它确实这样做了。但随后，合并的数组会从索引 0 开始复制回原始数组。相反，您需要确保原始数组仅在 lower 和 higher 之间修改:

for (var a = 0; a <= k; a++) {
    console.log(a);
    arr1[a + lower] = mergearr[a]; // <--- here
    console.log(arr1[a + lower]);
}