Search code examples
algorithmmergesort

Running time of k sorted arrays?

Suppose we are given k sorted arrays, each with n elements, and we want to combine them into a single array of kn elements.

My Approach: My approach is to use the Merge subroutine repeatedly, first merging the first two arrays, then merging the result with the third array, then with the fourth array, and so on until I merge in the kth and final input array. My question is what will be the running time taken by this successive merging algorithm, as a function of k and n, ignoring constant factors and lower-order terms?

Merge subroutine:

 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
Solution

  • The running time will be O(k^2 * n). The reason is that the i'th merge takes O(i*n + n) time to do, and there are approximately k/2 such merges with i > k/2.

    There is a reason that in the classic mergesort we merge each half of the arrays separately, and only then merge the two sorted arrays together...