javascript - 在 Javascript 中合并 n 个排序数组

Question

我有 n 个(n 在 1 到 100 之间)排序的数字数组，每个数组有 m 个元素(在我的例子中 m 大约为 1000)。我想将它们合并到一个排序的数组中。

我可以想到这样做的两种可能性:

1.使用两个数组合并算法(比如下面来自 http://www.nczonline.net/blog/2012/10/02/computer-science-and-javascript-merge-sort/ 的 merge() 函数)并迭代应用它(第 1 和第 2，然后合并第 1-2 和第 3，等等)

  function merge(left, right) {
      var result  = [],
        il      = 0,
        ir      = 0;
      while (il < left.length && ir < right.length){
        if (left[il] < right[ir]){
            result.push(left[il++]);
        } else {
            result.push(right[ir++]);
        }
    }
    return result.concat(left.slice(il)).concat(right.slice(ir));
}

1. 将 merge() 函数同时推广到 n 个数组。在每次迭代中，我会选择 n 个尚未处理的第一个值中的最小值并将其附加到结果中。

这两个算法在复杂性方面是否相同？我感觉这两种算法都在 o(m*n) 中。我说得对吗？

采用一种算法而不是另一种算法是否有任何性能考虑？我感觉 1 比 2 简单。

Answer 1

使用优先级队列(例如基于二叉堆)合并 n 个数组。
整体元素数为 m*n，因此算法复杂度为 O(m * n * Log(n))。算法示意图:

Add numbers 1..n to priority queue, using 1st element of every 
array as sorting key 
(you may also use pairs (first element/array number).
At every step - 
  J = pop_minimum
  add current head of Jth array to result
  move head of Jth array to the right
  if Jth array is not exhausted, insert J in queue (with new sorting key)

第一个算法的复杂度是

2*m + 3*m+ 4*m+...+n*m = m * (n*(n-1)/2-1) =  O(n^2 * m)