10-04-2017, 08:03 PM
k -way-merge. Suppose you are given k sorted arrays, each with n elements, and you
want to combine them into a single array of kn elements. Consider the following approach.
Using the merge subroutine , you merge the first 2 arrays, then merge the
3rd given array with this merged version of the first two arrays, and so on until you merge in
the final ( k[/size][/font]th ) input array. What is the time taken for this strategy, as a function of
k and n ? [Can you think of a better algorithm to solve the problem?]
[ASSIGNMENT]
k -way-merge. Suppose you are given k sorted arrays, each with n elements, and you
want to combine them into a single array of kn elements. Consider the following approach.
Using the merge subroutine we saw in class, you merge the first 2 arrays, then merge the
3
rd given array with this merged version of the first two arrays, and so on until you merge in
the final ( k
th ) input array. What is the time taken for this strategy, as a function of
k and n ? [Can you think of a better algorithm to solve the problem?]