The Ford-Johnson Sorting Algorithm Is Not Optimal
Glenn K. Manacher · Journal of the ACM · 1979
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 [log t I] for l -- 189, for which F(t) -S(t) = kt -O(log t) 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.