Optimal Merge Pattern

When more than two sorted files are merged together, the merge can be accomplish by repeatedly merging sorted files in pairs. Thus if the files x₁, x₂, x₃ and x₄ are to be merged then we would have to merge first x₁ and x₂ to get result y₁ then y₁ and x₃ to get y₂ and then y₂ to x₄ to get result y₃ desired sorted files. Alternatively, we also do the merging of files x₁ and x₂ to get the result y₁ then merge file x₃ and x₄ to get y₂ and at last merge y₁ and y₂ to get sorted files. For example the files x₁, x₂, and x₃ are the three sorted files with the length 30, 20 and 10 records each. If we merge x₁ and x₂ then we get 50 moves and then if we merge with x₃ we get another 60 moves.
       Alternatively by this method we give the merging file of about 110 moves.

At another method if we merged x₂ and x₃ and then x₁ then total record moves is only 90.

Hence the second merge pattern is faster than the first one.

Algorithm for optimal merge pattern

Algorithm Tree (n)

{

For i=1 to n-1 do

{

pt = new treenode ;    // get tree node

( pt →  lchild ) = least ( list ) ;  // merge two tree with smallest length s

( pt →  rchild ) = least ( list ) ;

( pt →  weight ) = ( ( pt→ lchild ) → weight ) + ( ( pt →  rchild ) → weight ) ;

Insert ( list, pt ) ;

}

// Tree left in list is merge tree

return least ( list ) ;

}