JavaScript归并排序运行出现最大调用栈超限报错
归并排序栈溢出问题定位与修正
核心报错与运行异常原因
递归缺少终止边界(直接触发栈溢出的根源)
当前mergeSort没有设置递归停止条件,只要入参数组长度大于0就会持续切分:
当数组长度为1时,mid = Math.floor(1/2) = 0,左数组切分为arr.slice(0,0)即空数组,右数组切分为arr.slice(0)也就是当前这个长度为1的原数组;如果是空数组,切分结果依然是两个空数组,递归会无限循环调用,直接触发最大调用栈超限。merge函数没有返回值merge内部最后执行sorted.concat(...)时,concat会生成新数组但没有被return,导致merge的返回值永远是undefined,就算解决了栈溢出,后续合并逻辑也完全无法运行。主函数没有返回排序结果
doMergeSort内部调用了mergeSort(array),但没有把这个返回值抛出,外部调用方拿不到排序后的数组。
修正后的可运行代码
export const doMergeSort = (array) => { const mergeSort = arr => { // 新增递归终止条件:数组长度≤1时直接返回,不再切分 if (arr.length <= 1) return arr; let mid = Math.floor(arr.length / 2), left = mergeSort(arr.slice(0, mid)), right = mergeSort(arr.slice(mid)); return merge(left, right); }; const merge = (arr1, arr2) => { let sorted = []; while (arr1.length && arr2.length) { if (arr1[0] < arr2[0]) sorted.push(arr1.shift()); else sorted.push(arr2.shift()); }; // 新增return,返回合并后的完整数组 return sorted.concat(arr1.slice().concat(arr2.slice())); }; // 新增return,把排序结果抛出给调用方 return mergeSort(array); }
可选优化建议
当前merge里用shift()每次移除数组头部元素,时间复杂度为O(n),会拉低整体排序性能,可替换为双指针对比的实现方式,减少不必要的数组重排开销。
内容的提问来源于stack exchange,提问作者John kant
相关产品推荐
相关产品推荐

