这种合并排序的迭代实现正确吗

Question

这对我来说似乎很简单。请注意，这并不是通过一分为二来生成单个元素数组，而是通过使用单个循环来生成。

function mergeSort(arr) {
for (let i = 0; i < arr.length; i++) {
arr[i] = [arr[i]]
}
while (arr.length > 1) {
for (let i = 0; i < arr.length; i = i + 2) {
arr.splice(i, 2, mergeTwoSortedArrays(arr[i], arr[i + 1] || []))
}
}
return arr[0]
}

我的测试通过了，但也许时间/空间的复杂性没有那么好？

Answer 1

arr.splice(i, 2, ...)将需要移动i之后的内容，因此这不是一个恒定的时间操作，因此您超过了使用合并排序所期望的O(nlogn(的时间复杂性。

为了解决这个问题，我建议根本不要从数组中拼接任何东西，而只是跳过不再相关的数组条目。

function mergeSort(arr) {
for (let i = 0; i < arr.length; i++) {
arr[i] = [arr[i]];
}
for (let step = 1; step < arr.length; step *= 2) {
for (let i = 0; i + step < arr.length; i += step*2) {
arr[i] = mergeTwoSortedArrays(arr[i], arr[i+step]);
delete arr[i+step]; // optional; to have it garbage collected
}
}
return arr[0];
}
function mergeTwoSortedArrays(a, b) {
let merged = [];
let i = 0, j = 0;
while (i < a.length || j < b.length) {
merged.push(
i < a.length && (j >= b.length || a[i] < b[j])
? a[i++]
: b[j++]
);
}
return merged;
}
let arr = Array.from({length: 1000}, () => Math.floor(Math.random() * 1000000));
let sorted = mergeSort([...arr]);
let sorted2 = arr.sort((a,b) => a-b); // verify
console.log(sorted+"" === sorted2+""); // output verification result

Answer 2

这是O(n^2)，但具有良好的常量。

问题是arr.splice是一个O(n)操作，无法对其进行优化。您需要从数组的中间取出2个值，然后必须将其他值移到上面。该移动操作经过了高度优化，但仍然是O(n)。

相反，使用shift/push来解决该问题。这将导致元件"；"旋转"；通过阵列。(实际上，数组会在内存中移动，直到它被移动，然后再次在内存中运行。但这一切都应该得到很好的优化。(

function mergeSort(arr) {
for (let i = 0; i < arr.length; i++) {
arr[i] = [arr[i]]
}
while (arr.length > 1) {
let elt1 = arr.shift()
let elt2 = arr.shift()
arr.push(mergeTwoSortedArrays(elt1, elt2))
}
return arr[0]
}

(旁注，我保留了你的风格。但天哪，我想在几个地方撒;吗？(