Ruby:堆栈级别太深(SystemStackError)实现合并排序与倒置计数

Question

这是我的代码。

@@inversions = 0
numbers = [very big array]

def merge_sort(array)
  return array if array.size <= 1

  left = array.slice(0, (array.size / 2).round)
  right = array - left
  merge(merge_sort(left), merge_sort(right))
end

def merge(left, right)
  return right if left.empty? # crashes here with stack level too deep
  return left if right.empty?

  if left.first <= right.first
    [left.first] + merge(left[1..-1], right)
  else
    @@inversions += left.size
    [right.first] + merge(left, right[1..-1])
  end
end

你能告诉我失败的原因吗？ (适用于大小小于 ~ 15000 的数组)

Answer 1

您的递归合并功能可能是原因。对于数组中的每个元素，您将在堆栈中更深一层。标准归并排序不应比 lg(N) 更深。尝试将 merge 重写为迭代而不是递归。

有点像

def merge left,right
  a = []
  while !left.empty? and !right.empty?
    if left.first < right.first
       a<<left.shift
    else 
       a<<right.shift
    end
  end
  a + left + right
end