FORD-JOHNSON SORTING ALGORITHM IS NOT OPTIMAL

One way of expressing the efficiency of a sorting algorithm is m terms of the number of palrwise comparisons required in the worst case to sort t items The most effioent algomhm known is that of Ford and Johnson [FJA], which achieves the “information-theoretic” lower bound [formula omitted] No value of t has been discovered for which S(t) < F(t), where S(t) is the smallest number of comparisons required and F(t) is the number of comparisons required by the FJA It has been uncertain since the FJA first appeared in 1959 whether it is optimal in the sense that F(t) = S(t) for all t It is shown that this is not the case, and it ts shown constructively how to compute infinitely many t, t ≥ 189, for which [formula omitted] for posiuve k The method is intimately related to the fact that substantial improvements to the merging algorithm of Hwang and Lm are possible, as shown in a companion paper. © 1979, ACM. All rights reserved.