执行合并排序算法时系统堆栈出错

Question

我使用递归进行合并排序算法，这可能是堆栈溢出的原因。我已经搜索过，但似乎无法找出导致所有这些代码的哪一部分。

这是我的代码：

  def merge(arr)
    return arr if arr.length <= 1
    mid = arr.length/2
      x = arr[0..mid]
      y = arr[mid..-1]
      merge_sort(merge(x),merge(y))
    end
    def merge_sort(left, right)
      sorted = []
      while left.length > 0 && right.length > 0
        if left.first > right.first
          sorted << left.shift
        else
          sorted << right.shift
        end
    end
      sorted.concat(left).concat(right)
    end

nums = 15.times.map {rand(100) + 1}
puts merge(nums)

在终端中我得到：merge-sort.rb：2：堆栈级别太深（SystemStackError）

Answer 1

在 Ruby 中，... 是端点独占的，..是端点包含的。这意味着您的x ，y都包含arr[mid] 。

改变

x = arr[0..mid]

自

x = arr[0...mid]    

它应该有效。

见 http://www.ruby-doc.org/core-2.1.5/Range.html