合并排序实现JavaScript

Question

我试图在JavaScript中实现合并排序算法，而没有内置的方法，如slice()， splice()等。它并不像我希望的那样起作用。你能帮我找出虫子藏在哪里吗?输出[3,5,5,3,7]而不是[3,5,5,7,8]

// Merge Sort implementation
// sort implementation
function sort(arr, start, mid, end) {
// Creation and filling the temp arrays
let lArray = [];
let rArray = [];
for (let i = 0; i <= mid - start; i++) {
lArray[i] = arr[start + i];
}
for (let j = 0; j <= end - mid - 1; j++) {
rArray[j] = arr[mid + 1 + j];
}

// Sorting and updating current array
let i = 0;
let j = 0;
let k = start;
while (i < lArray.length && j < rArray.length) {
if (lArray[i] < rArray[j]) {
arr[k] = lArray[i];
i++;
k++;
} else {
arr[k] = rArray[j];
j++;
k++;
}
}
// Handling last element in lArray or rArray
i < lArray.length ? arr[k] = lArray[i] : arr[k] = rArray[j];
}
// Recursive Merge Sort 
function recursiveMergeSort(arr, start, end) {
if (start < end) {
let mid = Math.floor(((end) + start) / 2);
//console.log(start, end, mid);
recursiveMergeSort(arr, start, mid);
recursiveMergeSort(arr, mid + 1, end);
sort(arr, start, mid, end);
}
}
function mergeSort(arr) {
let start = 0;
let end = arr.length - 1;
recursiveMergeSort(arr, start, end);
return (arr)
}
console.log(mergeSort([5, 8, 3, 7, 5]));

Answer 1

// Handling last element in lArray or rArray不正确

合并数组后，必须检查剩余部分并复制未处理的尾部，如果它确实存在

while (i < lArray.length) {
arr[k] = lArray[i];
i++;
k++;
}
while (j < rArray.length) {
arr[k] = rArray[j];
j++;
k++;
}

用下面的代码替换三元运算符可以得到给定数据的正确结果

Answer 2

一个自顶向下归并排序的优化版本的例子。它对工作数组进行一次分配，并使用一对相互递归的函数来改变每个递归级别的合并方向。在我的系统上对100万个伪随机整数进行排序大约需要1/4秒:

// merge sort top down
function merge(a, b, bgn, mid, end) {
var i = bgn                           // left:  a[bgn,mid)
var j = mid                           // right: a[mid,end)
var k = bgn                           // index for b[]
while(true){
if(a[i] <= a[j]){                   // if left <= right
b[k++] = a[i++]                   //   copy left
if(i < mid)                       //   if not end of left
continue                        //     continue back to while
do                                //   else copy rest of right
b[k++] = a[j++]
while(j < end)
break                             //     and break
} else {                            // else left > right
b[k++] = a[j++]                   //   copy right
if(j < end)                       //   if not end of right
continue                        //     continue back to while
do                                //   else copy rest of left
b[k++] = a[i++]
while(i < mid)
break                             //     and break
}
}
}
function sortatob(a, b, bgn, end) {     // sort a to b
if ((end-bgn) < 2){
b[bgn] = a[bgn]
return
}
var mid = Math.floor(bgn + (end - bgn) / 2)
sortatoa(a, b, bgn, mid)
sortatoa(a, b, mid, end)
merge(a, b, bgn, mid, end)
}
function sortatoa(a, b, bgn, end) {     // sort a to a
if ((end-bgn) < 2)
return
var mid = Math.floor(bgn + (end - bgn) / 2)
sortatob(a, b, bgn, mid)
sortatob(a, b, mid, end)
merge(b, a, bgn, mid, end)
}
function mergesort(a) {                 // entry function
if(a.length < 2)
return
var b = new Array(a.length)           // allocate temp array
sortatoa(a, b, 0, a.length)           // start with sort a to a
}
var a = new Array(1000000)
for (i = 0; i < a.length; i++) {
a[i] = parseInt(Math.random() * 1000000000)
}
console.time('measure')
mergesort(a)
console.timeEnd('measure')
for (i = 1; i < a.length; i++) {
if(a[i-1] > a[i]){
console.log('error')
break
}
}