Bounds on Optimal Merge Performance, and a Strategy for Optimality

Abstract

The length of a sorted sequence produced by the internal sort phase of a large scale general purpose sort routine is a random variable. In a random access environment, any given set of such sequences can be merged in an optimal way, and in practice this is often done. The expected work per item required by an optimal merge depends upon the probability distribution for sequence length, and it is this dependence which is studied in this paper. Reasonably sharp upper and lower bounds are derived. The distribution which is optimal in the sense of minimizing the lower bound on any bounded interval is determined, and it is shown that this is the strongest result of its kind. © 1972, ACM. All rights reserved.