Optimal merge pattern

 

Optimal merge pattern is a pattern that relates to the merging of two or more sorted files in a single sorted file. Here, we merge a set of sorted files of different length into a single sorted file. We need to find an optimal solution, where the resultant file will be generated in minimum time.

If the number of sorted files are given, there are many ways to merge them into a single sorted file. This merge can be performed pair wise. Hence, this type of merging is called as 2-way merge patterns. As, different pairings require different amounts of time, in this strategy we want to determine an optimal way of merging many files together. At each step, two shortest sequences are merged.

If we have two files of sizes m and n, the total computation time will be m+n. Here, we use the greedy strategy by merging the two smallest size files among all the files present.

Let’s illustrate with examples:-

 

1. Find optimal merge tree for the given unsorted files -5, 3, 2, 7, 9, 13. Also find the total cost of merging.

Let’s name the unsorted files as :-

A   B   C   D   E   F

5   3   2   7   9   13

 

Now to find the optimal solution we first need to sort the given data and arrange it in sequential manner, as this allows us to find the shortest path and thus the optimal solution.

 

    C       B       A       D       E         F

    2       3       5       7        9        13

 

Let us now apply optimal merging on the given data:-

 

Hence, merge operations can be performed on this sequence

 

M1 = merge C and B => 2 + 3 = 5

M2 = merge M1 and A => 5 + 5 = 10

M3 = merge M2 and F => 10 + 13 = 23

M4 = merge D and E => 7+ 9 = 16

M5= merge M4 and M3 => 23 + 16 = 39

Therefore, Total Cost:-5+10+16+23+39=93.

Which is the optimal solution using optimal merge pattern.

 

2. Find the optimal merge tree for ten files whose length is :- 28,32,121,84,53,91,35,3 and 11 Also find its weighted external path length.

 

To find the optimal solution we first sort the given data and arrange it in ascending order as:-

3          5      11        12           28             32         35          53         84           91

     

       Now let’s apply the merge on the sorted data to get the optimal merge tree.

3          5      11        12           28             32         35          53         84           91

The weighted external path length = 8+19+31+59+67+112+151+203+354=1004

 

___________________________________________________________________________________Submitted By;

Ankita Kakade

Roll No:45