Abstract
For almost twenty years, the Ford-Johnson algorithm for sortingt items using comparisons was believed to be optimal. Recently, Manacher was able to show that the Ford-Johnson algorithm is not optimal for certain ranges of values oft. In this paper, we present some new algorithms which achieve much stronger results compared to Manacher's algorithms.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
T. D. Bui and Thanh Mai,Efficient algorithms for sorting by comparisons. Department of Computer Science Report, Concordia University, Montreal, Québec, Canada.
C. Christen,Improving the bounds on optimal merging. Proc. 19th Annual IEEE Conf. on the Foundations of Comp. Sci., (1978), 259–266.
L. R. Ford Jr. and S. M. Johnson,A tournament problem. AMM 66, 5 (1959), 387–389.
F. K. Hwang and S. Lin,A simple algorithm for merging two disjoint linearly — ordered sets. SIAM J. Computing 1, 1 (1972), 31–39.
D. E. Knuth,The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley, Reading, Mass., (1973), 181–209.
Thanh Mai and T. D. Bui,An improvement of the binary merge algorithm. BIT 22 (1982), 454–461.
G. K. Manacher,The Ford-Johnson sorting algorithm is not optimal. J. ACM 26, 3 (July 1979), 441–456.
G. K. Manacher,Significant improvements to the Hwang-Lin merging algorithm. J. ACM 26, 3 (July 1979), 434–440.
G. K. Manacher,Further results on near-optimal sorting. Proceedings of the Allerton Conference on Communication, Control and Computing, (1979), 949–960.
J. Mönting,Optimal merging of 3, 4 and 5 elements with N elements, Technical Report, (1978), Mathematisches Institut, Tübingen, Germany.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Bui, T.D., Thanh, M. Significant improvements to the Ford-Johnson algorithm for sorting. BIT 25, 70–75 (1985). https://doi.org/10.1007/BF01934989
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01934989