Optimal disk merge patterns

Our purpose is to study the optimal way to merge n initially sorted runs, stored on a disk like device, into a unique sorted file. This problem is equivalent to finding a tree with n leaves which minimizes a certain cost function (see Knuth 1]).We shall study some properties of those optimal trees, in the hope of finding efficient ways for constructing them.In particular, if all the initial runs have the same length, an algorithm for constructing the best merge pattern is described ; its running time is proportional to n ² and it requires space proportional to n.A special case is also analyzed in which the problem is solved in time and space proportional to n, and which provides some insight into the asymptotic behaviour of optimal merge trees.