ruby - 执行合并排序算法的系统堆栈错误

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: Stack level too deep (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