K分类数组的运行时间

Question

假设我们得到了k排序的数组，每个数组都有n个元素，我们希望将它们组合成一个kn元素。

我的方法：我的方法是反复使用合并子例程，第一次合并第一个阵列，然后将结果与第三阵列合并，然后使用第四个阵列，依此类推，直到我在KTH和最终输入阵列中合并。我的问题是，作为K和N的函数，这种连续合并算法所花费的运行时间是什么，忽略了恒定的因素和低阶项？

合并子例程：

 i := 1 
 j := 1 
 for k := 1 to n do 
   if C[i] <D [j] then 
      B[k] :=C[i] 
      i := i +1 
   else 
      B[k] :=D[j] 
      j := j +1

Answer 1

运行时间为 O(k^2 * n)。原因是i'TH合并需要O(i*n + n)的时间，并且大约有k/2与i > k/2合并。

有一个原因，在经典的Mergesort中，我们分别合并了每个阵列的每个半数，然后将两个排序的数组合并在一起...