It is demonstrated, using a combination of theoretical and experimental computer science, that there is no nine-input sorting network of depth six. If a nine-input sorting network of depth six exists, then there exists one with very special structure. There is an efficient algorithm for constructing and testing comparator networks of this form. This algorithm was implemented and executed on a supercomputer.
%0 Journal Article
%1 noKey
%A Parberry, Ian
%D 1991
%I Springer-Verlag
%J Mathematical systems theory
%K algorithm sorting sorting.network
%N 1
%P 101-116
%R 10.1007/BF02090393
%T A computer-assisted optimal depth lower bound for nine-input sorting networks
%V 24
%X It is demonstrated, using a combination of theoretical and experimental computer science, that there is no nine-input sorting network of depth six. If a nine-input sorting network of depth six exists, then there exists one with very special structure. There is an efficient algorithm for constructing and testing comparator networks of this form. This algorithm was implemented and executed on a supercomputer.
@article{noKey,
abstract = {It is demonstrated, using a combination of theoretical and experimental computer science, that there is no nine-input sorting network of depth six. If a nine-input sorting network of depth six exists, then there exists one with very special structure. There is an efficient algorithm for constructing and testing comparator networks of this form. This algorithm was implemented and executed on a supercomputer.},
added-at = {2014-04-20T16:40:54.000+0200},
author = {Parberry, Ian},
biburl = {https://www.bibsonomy.org/bibtex/23889a01f7970f183258dd5da19b6bdd4/ytyoun},
doi = {10.1007/BF02090393},
interhash = {3ec810952684ccda6336b2d24081f892},
intrahash = {3889a01f7970f183258dd5da19b6bdd4},
issn = {0025-5661},
journal = {Mathematical systems theory},
keywords = {algorithm sorting sorting.network},
language = {English},
number = 1,
pages = {101-116},
publisher = {Springer-Verlag},
timestamp = {2016-10-27T12:48:58.000+0200},
title = {A computer-assisted optimal depth lower bound for nine-input sorting networks},
volume = 24,
year = 1991
}