Oct 10, 2018

[HDGEM] A k-way merge operation.

Suppose you have k sorted arrays, each with n elements, and you want to combine them into a single sorted array of kn elements.
  1. Here's one strategy: Using the merge procedure, merge the first two arrays, then merge in the third, then merge in the fourth, and so on. What is the time complexity of this algorithm, in terms of k and n?
    ANSWER: Merging two sorted arrays A1 and A2 with n1 and n2 elements, respectively, takes O (n1 + n2) time. This strategy begins by merging two arrays of size n to create an array of size 2n. It then merges that with an array of size n, and so on. Thus, the running time is
    (n + n) + (2n + n) + (3n + n) + . . . + ((k 1)n + n))  = 2n+3n+4n+...+kn = O(k2n

Posted By Blogger to HDGEM at 3/06/2017 09:34:00 PM