ADA: Greedy Technique - Optimal Merge Pattern

Optimal Merge Pattern

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.

To merge a p-record file and a q-record file requires possibly p + q record moves, the obvious choice being, merge the two smallest files together at each step.

Two-way merge patterns can be represented by binary merge trees. Let us consider a set of n sorted files {f₁, f₂, f₃, …, f_n}. Initially, each element of this is considered as a single node binary tree. To find this optimal solution, the following algorithm is used.

Problem Statement

Let there be a set of sorted sequences of the following lengths:

D={3 ,5 ,7 ,9 ,12 ,14 ,15 ,17}

Building the optimal merge tree to minimizing reads. Only two sequences can be merged at once. At each step, the two shortest sequences are merged.

Output

File: Download here