Titre du document / Document title
The Ford-Johnson algorithm still unbeaten for less than 47 elements
Auteur(s) / Author(s)
PECZARSKI Marcin
(1) ;
Affiliation(s) du ou des auteurs / Author(s) Affiliation(s)
(1) Institute of Informatics, Warsaw University, ul. Banacha 2, 02-097 Warszawa, POLOGNE
Résumé / Abstract
Using exhaustive computer search we show that sorting 15 elements requires 42 comparisons, and that for n < 47 there is no algorithm of the following form: "m and n - m elements are sorted using the Ford-Johnson algorithm first, then the sorted sequences are merged", whose total number of used comparisons is smaller than the number of comparisons used by the Ford-Johnson algorithm to sort n elements directly.
Revue / Journal Title
Information processing letters
ISSN 0020-0190
CODEN IFPLAT
Source / Source
2007, vol. 101, n
o3, pp. 126-128 [3 page(s) (article)] (16 ref.)
Langue / Language
Anglais
Editeur / Publisher
Elsevier, Amsterdam, PAYS-BAS
(1971)
(Revue)
Mots-clés anglais / English Keywords
Information processing ;
Computer theory ;
Algorithm analysis ;
Sorting ;
Merging ;
Mots-clés français / French Keywords
Nombre comparaisons ;
Algorithme tri ;
Traitement information ;
Informatique théorique ;
Analyse algorithme ;
Triage ;
Fusion(informatique) ;
Mots-clés espagnols / Spanish Keywords
Procesamiento información ;
Informática teórica ;
Análisis algoritmo ;
Tría ;
Mots-clés d'auteur / Author Keywords
Analysis of algorithms ;
Sorting ;
Merging ;
Localisation / Location
INIST-CNRS, Cote INIST : 15156, 35400015962328.0070
Nº notice refdoc (ud4) : 18416105
