Optimal Merge Pattern

Question

Given a set of sorted files f1,f2,f3,f4,f5 of lengths 99,27,71,199,259 we need to merge these files into a single sorted file Using Optimal Merge Pattern.

Comments

Here, you can relate it with the Huffman's coding. Try solving as if these file length are the frequencies for the character (there,Huffman coding).

You can draw the Huffman tree & then the sum of all all nodes (consider nodes which are the result of sum of two file length) will give the optimal merge complexity.

http://www.geeksforgeeks.org/greedy-algorithms-set-3-huffman-coding/

Answer 1

According to optimal merge pattern we take two minimal and merge it so given sequence is:

f1	99
f2	27
f3	71
f4	199
f5	259

we arrange sequence in ascending order

f2, f3, f1, f4, f5

M1: Merge f2 and f3 :: 27+71 = 98

M2: Merge  M1 and  f1 _:: 98+99 = 197

M3: Merge M₂ and f4:: 197+199 = 396

M4 Merge M₃ and f5:: 396+259 = 655