Significant improvements to the Ford-Johnson algorithm for sorting

descriptionPublicationkeyboard_double_arrow_right Article 01 Mar 1985 English Publisher:Springer Science and Business Media LLCJournal:BIT, volume 25, pages 70-75 (issn: 0006-3835, eissn: 1572-9125,

Copyright policy )

Authors: Tien Dai Bui; Mai Thanh;

doi: 10.1007/bf01934989

Significant improvements to the Ford-Johnson algorithm for sorting

- Summary
- Subjects
- Metrics

Abstract

The authors present a sorting by comparison algorithm and discuss its performances. The algorithm is an improvement of an algorithm proposed by \textit{G. K. Manache} [J. Assoc. Comput. Mach. 26, 441-456 (1979; Zbl 0404.68063)] as a more efficient version of the known Ford-Johnson sorting algorithm. Authors' contribution is based on a merging algorithm for two lists, proposed by \textit{C. Christen} [Improving the bounds on optimal merging, Proc. 19th Annual IEEE Conf. on the Foundations of Computer Sci., 259-266 (1978)]. The proofs for the stated results are not included in this paper.

Related Organizations

Concordia University
Canada
CONCORDIA UNIVERSITY
Canada

Keywords

sorting by comparison, Analysis of algorithms and problem complexity, Searching and sorting

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	2
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average