两个JavaScript归并排序实现差异解析：为何Sample1输出错误？

实现代码对比 #

Sample 1（错误实现） #

function mergesort(arr){    
    if (arr.length > 1){        
        let mid = parseInt(arr.length/2);        
        let left = arr.slice(0,mid);        
        let right = arr.slice(mid);        
        mergesort(left);        
        mergesort(right);          
        return merge(left,right);    
    }    
    else return arr;
}

Sample 2（正确实现） #

function mergesort(arr){    
    if (arr.length > 1){        
        let mid = parseInt(arr.length/2);        
        let left = mergesort(arr.slice(0,mid));        
        let right = mergesort(arr.slice(mid));           
        return merge(left,right);    
    }    
    else return arr;
}

Merge 辅助函数 #

function merge(left, right){    
    let leftIdx = 0, rightIdx = 0;     
    const result = [];    
    while (leftIdx < left.length && rightIdx < right.length){        
        if (left[leftIdx] < right[rightIdx]){            
            result.push(left[leftIdx++])        
        }        
        else{            
            result.push(right[rightIdx++])        
        }    
    }    
    let res = [...result, ...left.slice(leftIdx), ...right.slice(rightIdx)];    
    return res;
}

测试用例 #

测试数组：

let arr = [5, 3, 7, 2, 9, 12, 4];

测试结果：

• Sample 2 输出正确排序结果：[2, 3, 4, 5, 7, 9, 12]
• Sample 1 输出错误结果：[2, 5, 3, 7, 9, 12, 4]

差异原因解释 #

核心区别在于递归调用后是否接收返回的排序结果：

• Sample 1 中，mergesort(left)和mergesort(right)只是执行了递归，但没有把递归返回的排序后数组赋值给left和right变量。这里的left和right始终是最初从原数组切片得到的未排序片段，最后merge(left, right)合并的是两个未排序的数组，自然得不到正确结果。
• Sample 2 中，left = mergesort(arr.slice(0,mid))和right = mergesort(arr.slice(mid))直接把递归返回的排序后数组赋值给了left和right，后续merge操作的是两个已经排好序的子数组，这才符合归并排序“分-治-合”的逻辑：先把每个子数组递归排序，再合并两个有序子数组。

简单说，Sample 1犯了一个低级错误——调用递归但不用它的返回值，等于白排序了子数组，最后合并的还是原始切片的乱序数组。

内容的提问来源于stack exchange，提问作者Hasibul Alam