Titre du document / Document title

The Ford-Johnson algorithm still unbeaten for less than 47 elements

Auteur(s) / Author(s)

PECZARSKI Marcin ⁽¹⁾ ;

Affiliation(s) du ou des auteurs / Author(s) Affiliation(s)

⁽¹⁾ 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 Science, 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