递归归并排序算法

Question

所以我正在研究一个算法问题，我真的很困惑正确的答案应该是什么样子。我有一个答案，但如果有人能给我反馈/指导，我将不胜感激。

问题：

Casc Merge is a recursive algorithm: Assume there     
are n sorted lists, each of size m. Recursively 
Casc Merge the first n − 1 lists and then
Merge the last list (of size m) into the sorted list A (which is of size (n-1)m).

1)Write down code for it

到目前为止，我的想法是这样的。看起来我似乎走在了正确的道路上，但就像我说的那样，我不知道。我试着用谷歌搜索，但没有得到太多帮助

proc Cas(A, L, c)
  if c == n then
     Merge(A, L[c-1], L[c])
  end if
  else
     Merge(A, Casc(A, L, c), Casc=(A, L, c+1))
  end else
end proc 

再次感谢您对伪代码的任何建议/反馈。

假设合并进行m+n-1次比较

S(n) = { 1                  if c = 1   
         S(n-1) + m - 1     otherwise   
}

Answer 1

我觉得你已经很接近了。不过，看起来您可能在基本情况附近有一个合并的“双重预订”，其中c==n，因为您正在将L[c-1]和L[c]合并到A中，但在之前的调用中，您已经执行了L[c-1]和L[c]的合并。

如果您从定义的角度考虑递归算法，您可以使用稍微简化的逻辑将其写出来：

procedure Cascade(List A, List[] L, int c)
   // base case (1-based indexing)
   if (c == 1) then
       Merge(A, L[c], {}) // merge the empty list with L[c] into A
   else
       // use the recursive definition
       Merge(A, L[c], Cascade(A, L, c-1))  // merge L[c] with L[c-1]
   end if
end procedure

你可以像这样调用这个过程：Cascade({}, L, n)

你可以像这样解决这个问题：

n = 3
L = {{1 2 3} {3 2 1} {4 5 6}}
A = {}

First call to Merge yields:
Merge(A, {4 5 6}, Cascade({}, {{1 2 3} {3 2 1} {4 5 6}}, 2))

Then:
n = 2
Merge(A, {3 2 1}, Cascade({}, {{1 2 3} {3 2 1} {4 5 6}}, 1))

Then:
n = 1 (base case)
Merge(A, {1 2 3}, {})

Trickling back up the chain (actual merge results not shown for clarity):
A = {1 2 3}
A = {1 2 3 3 2 1}
A = {1 2 3 3 2 1 4 5 6}  // merged list (the actual implementation would have sorted these...)

你就完事了！希望这能帮到你。

编辑:基于评论中充实的讨论，下面是一个使用返回传递数据的示例，而不是就地修改。

procedure Cascade(List[] L, int c)
   // base case (1-based indexing)
   if (c == 1) then
       A = Merge(L[c], {}) // merge the empty list with L[c] into A
   else
       // use the recursive definition
       A = Merge(L[c], Cascade(L, c-1))  // merge L[c] with L[c-1]
   end if
   Return A // return the newly merged list
end procedure