CODEWITHSUNDEEP
algorithmmergesort
3iL
3iL

Reputation: 2176

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

Upvotes: 0

Views: 316

Answers (1)

btilly
btilly

Reputation: 46455

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...

Upvotes: 1

Related Questions