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. 

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 pairwise merge can be done to get a single sorted file. 

Different pairings require a different amount of computing time.

The main thing is to pairwise merge the n sorted files so that the number of comparisons will be less.

Example:

Given a set of unsorted files: 5, 3, 2, 7, 9, 13

Now, arrange these elements in ascending order: 2, 3, 5, 7, 9, 13

After this, pick two smallest numbers and repeat this until we left with only one number.

Now follow following steps:

Step 1: Insert 2, 3

Step 2:

Step 3: Insert 5

Step 4: Insert 13

Step 5: Insert 7 and 9

Step 6:

So, The merging cost = 5 + 10 + 16 + 23 + 39 = 93