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.

An efficient bidirectional search algorithm for computing the free distance of convolutional codes is described.

The methods currently in use and previously proposed for the choice of a root in minimal storage tree sorting are in reality methods for making inefficient statistical estimates of the median of the sequence to be sorted. By making efficient use of the information in a random sample chosen during input of the sequence to be sorted, significant improvements over ordinary minimal storage tree sorting can be made. A procedure is proposed which is a generalization of minimal storage tree sorting and which has the following three properties: (a) There is a significant improvement (over ordinary minimal storage tree sorting) in the expected number of comparisons required to sort the input sequence. (b) The procedure is statistically insensitive to bias in the input sequence. (c) The expected number of comparisons required by the procedure approaches (slowly) the information-theoretic lower bound on the number of comparisons required. The procedure is, therefore, “asymptotically optimal.”

In this paper, methods for document retrieval are derived from algebraic coding theory. It is shown that these methods are efficient in information representation and that the amount of computation required in implementation is quite reasonable.