Sorting nine inputs requires twenty-five comparisons

Michael Codish, Luis Cruz-Filipe, Michael Frank, Peter Schneider-Kamp

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

Resumé

This paper describes a computer-assisted non-existence proof of 9-input sorting networks consisting of 24 comparators, hence showing that the 25-comparator sorting network found by Floyd in 1964 is optimal. As a corollary, the 29-comparator network found by Waksman in 1969 is optimal when sorting 10 inputs.

This closes the two smallest open instances of the optimal-size sorting network problem, which have been open since the results of Floyd and Knuth from 1966 proving optimality for sorting networks of up to 8 inputs.
OriginalsprogEngelsk
TidsskriftJournal of Computer and System Sciences
Vol/bind82
Udgave nummer3
Sider (fra-til)551-563
ISSN0022-0000
DOI
StatusUdgivet - 2016

Fingeraftryk

Sorting Networks
Sorting
Nonexistence
Optimality
Corollary

Emneord

  • Symmetry breaking

Citer dette

@article{3bc81d5196fd4f09b22b7d095b02e650,
title = "Sorting nine inputs requires twenty-five comparisons",
abstract = "This paper describes a computer-assisted non-existence proof of 9-input sorting networks consisting of 24 comparators, hence showing that the 25-comparator sorting network found by Floyd in 1964 is optimal. As a corollary, the 29-comparator network found by Waksman in 1969 is optimal when sorting 10 inputs.This closes the two smallest open instances of the optimal-size sorting network problem, which have been open since the results of Floyd and Knuth from 1966 proving optimality for sorting networks of up to 8 inputs.",
keywords = "Symmetry breaking",
author = "Michael Codish and Luis Cruz-Filipe and Michael Frank and Peter Schneider-Kamp",
year = "2016",
doi = "10.1016/j.jcss.2015.11.014",
language = "English",
volume = "82",
pages = "551--563",
journal = "Journal of Computer and System Sciences",
issn = "0022-0000",
publisher = "Heinemann",
number = "3",

}

Sorting nine inputs requires twenty-five comparisons. / Codish, Michael; Cruz-Filipe, Luis; Frank, Michael; Schneider-Kamp, Peter.

I: Journal of Computer and System Sciences, Bind 82, Nr. 3, 2016, s. 551-563.

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

TY - JOUR

T1 - Sorting nine inputs requires twenty-five comparisons

AU - Codish, Michael

AU - Cruz-Filipe, Luis

AU - Frank, Michael

AU - Schneider-Kamp, Peter

PY - 2016

Y1 - 2016

N2 - This paper describes a computer-assisted non-existence proof of 9-input sorting networks consisting of 24 comparators, hence showing that the 25-comparator sorting network found by Floyd in 1964 is optimal. As a corollary, the 29-comparator network found by Waksman in 1969 is optimal when sorting 10 inputs.This closes the two smallest open instances of the optimal-size sorting network problem, which have been open since the results of Floyd and Knuth from 1966 proving optimality for sorting networks of up to 8 inputs.

AB - This paper describes a computer-assisted non-existence proof of 9-input sorting networks consisting of 24 comparators, hence showing that the 25-comparator sorting network found by Floyd in 1964 is optimal. As a corollary, the 29-comparator network found by Waksman in 1969 is optimal when sorting 10 inputs.This closes the two smallest open instances of the optimal-size sorting network problem, which have been open since the results of Floyd and Knuth from 1966 proving optimality for sorting networks of up to 8 inputs.

KW - Symmetry breaking

U2 - 10.1016/j.jcss.2015.11.014

DO - 10.1016/j.jcss.2015.11.014

M3 - Journal article

VL - 82

SP - 551

EP - 563

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

SN - 0022-0000

IS - 3

ER -