Ruby实现归并排序遇栈溢出问题，递归调用存疑

云上老周

2026-5-27

解决Ruby归并排序递归的栈层级过深问题

嘿，我看到你在实现归并排序的拆分逻辑时踩了个常见的递归坑——栈层级过深，这完全是因为递归调用的参数没传对导致的，咱们来把它理顺！

问题根源

你当前的递归调用写的是：

mergeSort(arr,0,mid) #是否需注释此行？
mergeSort(arr,mid+1,arr.length-1) #或注释此行？

这里的问题在于，你每次递归都硬编码了起始索引（0）和结束索引（arr.length-1），这就导致递归永远无法收敛到最小的子数组（单个元素）。举个例子：第一次拆分后，左边递归还是从整个数组的开头到mid，下次递归依然会重复这个过程，无限循环下去，最终触发栈溢出。

修正后的拆分代码

正确的做法是，递归时要基于当前函数接收到的beginIndex和endIndex来划分区间，而不是每次都用整个数组的边界：

array = [5,1,8,3,4,6,11,2]

def mergeSort(arr, beginIndex, endIndex)
  if endIndex > beginIndex
    mid = (beginIndex + endIndex) / 2
    # 递归处理左半部分：当前区间的起点到mid
    mergeSort(arr, beginIndex, mid)
    # 递归处理右半部分：mid+1到当前区间的终点
    mergeSort(arr, mid + 1, endIndex)
    
    # 这里后续需要添加合并两个有序子数组的逻辑
    # merge(arr, beginIndex, mid, endIndex)
  end
end

mergeSort(array, 0, array.length - 1)

为什么这样能解决问题？

每次递归调用时，我们传入的是当前子数组的边界，而不是整个数组的边界。比如第一次调用处理[0,7]，拆分后左半部分是[0,3]，右半部分是[4,7]；下一层递归会把[0,3]拆成[0,1]和[2,3]，以此类推，直到子数组的endIndex <= beginIndex（也就是子数组只有一个元素），递归就会停止，不会无限循环。