Significant improvements to the Ford-Johnson algorithm for sorting

DOI10.1007/BF01934989MaRDI QIDQ1064782zbMATH OpenFDO

Authors B. George

Publication date 1985

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01934989

zbMATH Keywords

sorting by comparison

Mathematics Subject Classification ID

Searching and sorting (68P10) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• The Ford-Johnson algorithm still unbeaten for less than 47 elements
• A variant of the Ford-Johnson algorithm that is more space efficient
• scientific article; zbMATH DE number 4114045
• Efficient unbalanced merge-sort
• An efficient multiway merging algorithm

Cites work

• A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets
• A Tournament Problem
• An improvement of the binary merge algorithm
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• Significant improvements to the Ford-Johnson algorithm for sorting
• Significant Improvements to the Hwang-Lin Merging Algorithm
• The Ford-Johnson Sorting Algorithm Is Not Optimal

Cited in

(4)

• Significant improvements to the Ford-Johnson algorithm for sorting
• On partial sorting in restricted rounds
• On the average case of MergeInsertion
• A variant of the Ford-Johnson algorithm that is more space efficient

This page was built for publication: Significant improvements to the Ford-Johnson algorithm for sorting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1064782)