堆栈到深度使用合并排序

Question

我正在尝试使用递归实现合并排序。

def merge_sort(a,i,j)
  if i < j 
    merge_sort(a,i,j/2)
    merge_sort(a,j/2+1,j)
    merge(a,i,j/2,j/2+1,j)
  end
end

def merge(a,i,j,k,l)
  # No implementation yet
end

问题是我的实现导致堆栈太深了。对于这样小的数组，我不应该收到这个错误消息。我试图排序的数组只有五个元素。

b = [5,4,3,2,1]
p merge_sort(b,0,b.size - 1) # => results in 'stack to deep' message

Answer 1

这是朝着正确方向迈出的一步，它使Ruby变得更加宽容--就像它是如何更宽容的，另外，作为奖励，它有实际的名称而不是数学上的速记：

def merge_sort(arr,from = nil,to = nil)
  from ||= 0
  to ||= arr.length

  if (from < to)
    part = from + (to - from) / 2

    merge_sort(arr, from, part)
    merge_sort(arr, part + 1, to)

    merge(arr, from,part, part+1, to)
  end
end

def merge(a,from,j,k,l)
  # No implementation yet
end

b = [5,4,3,2,1]
merge_sort(b)

错误的原因是没有正确定义分区点。在长度为5的数组的原始代码中，切点为2，当进一步分割时，切点为2/1或1，而不是2+(5-3)/2或3。从那以后，一切都变得疯狂了，因为它做错了数学，无缘无故地不停地自我标榜。

Answer 2

我的问题是，我的中点公式是将递归抛到无限循环中，直到堆栈溢出。而不是

J/2+1

它应该是

(i+j) /2+1

塔德曼在他的版本更新中得到了正确的公式。