Optimal Merge Pattern

Optimal merge pattern is a pattern that specifies the merging of two or more sorted files in a single sorted file. This type of merging can be done by the two-way merging method. If we have two sorted files containing n and m records respectively then they could be merged together, to obtain one sorted file in time O (n+m). There are many ways in which merge can be done to get a single sorted file. Given n sorted files containing some records in each file .The problem is to merge the n sorted files to get a single sorted file with minimum number of comparisons/movements . An optimal merge pattern corresponds to a binary merge tree with minimum weighted external path length. The formula of external merging cost is: Sum(d(i) * q(i)) for all i where i is the number of files. Where, q(i) represents the number of records in each file and d (i) represents the depth. The function Tree algorithm uses the Greedy rule to get a two- way merge tree for n files. The algorithm contains an input list of n trees. There are three field child, rchild, and weight in each node of the tree. There are two functions Least (list) and Insert (list, pt) in a function tree. Least (list) obtains a tree in lists whose root has the least weight and return a pointer to this tree. This tree is deleted from the list. Function Insert (list, pt) inserts the tree with root tp into the list. The main for loop in this algorithm is executed in n-1 times. If the list is kept in increasing order according to the weight value in the roots, then Least (list) needs only O(1) time and Insert (list, tp) can be performed in O(n) time. Hence, the total time taken is O (n^2). If the list is represented as a minheap in which the root value is less than or equal to the values of its children, then Least (list) and Insert (list, tp) can be done in O (log n) time. In this condition, the computing time for the tree is O (n log n).