In internal sorting by comparing pairs of elements, it is usually the case that the choice of the next, pair of elements to be compared depends upon the outcome of previous comparisons. However, in some situations it might be desirable instead to fix the sequence of comparisons, since this would tend to simplify the logic.

The shortest known fixed sequence of comparisons is one introduced recently by Bose and Nelson [1]. When n is the number of elements to be sorted, the sequence has length approximately 3~ g2'. This number is large compared with the average length, on the order of n log2 n, obtainable with negligible extra storage when the sequence is allowed to vary [2, 3, 4]. Nevertheless, the shortest known fixed sequence is necessarily worthy of note. The efficient utilization of the Bose-Nelson sequences is an interesting problem in itself, and is the subject of this note. The Bose-Nelson procedure is not, strictly speaking, a sorting algorithm, but rather a procedure for calculating a sequence of comparisons (called" P-operators" in [1]) with which a sorting algorithm can be constructed. To employ the method directly on a computer would therefore entail storing about 3~ g< integer pairs ill memory before starting to sort. We present, here an especially simple algorithm, with a negligible storage requirement, for generating the comparisons one by one in the order in which they are needed for sorting.