Question

Optimal Merge Pattern - We saw from MergeSort that merging two sorted files together (one size m and one size n) took O(m+n) time. When merging multiple sorted files together, the merge can be accomplished by repeatedly merging sorted files in pairs. For example X1, X2, X3 are three sorted files of length 30, 20 and 10. There are multiple ways to merge them two-at-a-time (with the appropriate costs):

(X1 merge X2) merge X3 X1 merge (X2 merge X3) (X1 merge X3) merge X2
cost=50 cost=60 cost=60 cost=30 cost=40 cost=60
total cost=110 total cost=90 total cost=100

Different pairings require different amounts of computing time. How would you solve this problem to find the optimal way to merge the files two-at-a-time. Prove the required properties of the problem and for your solution approach.

Answer 1

For merging multiple sorted files,

suppose that we have n file x1,x2,.....,xn having size s1,s2,......,sn respectively.

for merging optimally we use greedy approach,In which

we first create stack of files in which we have inserted file in descending order that means we first push file which has highest size and after that push file which has second highet size and like that push all files in stack so that stack's top contain file which has lowest size.

Now pop two files from stack and merge them and then calculate size of resulting file and put it in stack and after that sort stack array in descending order.

again pop two files from stack and repeat above process.

After repeating this process many times finally you get resultant file with minimum cost.

if you have any query then feel free to ask in comment.