Given n sorted files, the task is to find the Optimal Merge Pattern with the fewest computations. The Optimal Merge Pattern is used when two or more sorted files are to be merged to form a single file. This file is reached by performing the fewest computations. If you need to merge more than two files, you can do so in pairs. For example, suppose you need to merge four files: A, B, C, and D. First, combine A and B to get X1, then combine X1 and C to get X2, and finally combine X2 and D to get X3 as the output file.
The total computation time for two files of size m and n is m+n. In this case, we employ the greedy strategy, merging the two files with the smallest size among all the files present.
Suppose we have two lists, A, which has length m, and B with length n, and the merged list is C. It will cost O(m+n)
So, if we have more than 2 list. Let's find out the merged list for those lists.
Merge pattern-1
Cost = 11+13+16=40
Merge Pattern-2
Cost = 11+5+16 = 32
Merge Pattern-3
Cost = 16+10+5 = 31
So, we can see multiple merge patterns can be created from those 4 lists with different costs. We have to find out the optimal value. Remember, there may be more than one solution or pattern, but there must be only one optimal value. So now Be Greedy!!!
Suppose, we have five lists (x1, x2, x3, x4, x5) with the size of (20, 30, 10, 5, 30). We have to find out the optimal merge pattern with minimum cost.
- First, we have to sort the list in ascending order of size.
- Then merge the lowest size list and make a node.
- Continue the same process for the rest of the elements.
Total Cost= 15+35+95+60 = 205
We have another way to calculate the cost. The formula is given below-
Total Cost = 3 * 5+ 3 * 10 + 2 * 20 + 2 * 30 + 2 * 30 =205