Sorting networks fascinate me.
They even got me mentioned in Knuth Vol. 3,
p. 666 of the second edition.
My coauthor in this work is my Penn State
PhD student
Bruce Parker.
Ian Parberry,
"The Pairwise Sorting Network".
Parallel Processing Letters, Vol. 2, No. 2,3, pp. 205-211, 1992.
[pdf,
more information]
Abstract
A new sorting network with exactly the same size and depth as the odd-even sorting
network is presented. This sorting network is designed using the zero-one principle,
and proceeds by first sorting pairs of bits and sorting the pairs
into lexicographic order.
Ian Parberry,
"On the Computational Complexity of Optimal
Sorting Network Verification".
Proceedings of The Conference on
Parallel Architectures and Languages Europe,
Springer-Verlag Lecture Notes in Computer Science,
Vol. 506, pp. 252-269, June 1991.
[pdf]
Abstract
A sorting network is a combinational circuit for sorting, constructed from comparison-swap units.
The depth of such a circuit is a measure of its running time. It is reasonable to hypothesize that only
the fastest (that is, the shallowest) networks are likely to be fabricated. It is shown that the problem
of verifying that a given sorting network actually sorts is Co-NP complete even for sorting networks of
depth only $4 \log n + O(1)$ greater than optimal. This is shallower than previous depth bounds by a
factor of two.
Ian Parberry,
"Single-Exception Sorting Networks and the Computational Complexity of
Optimal Sorting Network Verification".
Mathematical Systems Theory, Vol. 23, pp. 81-93, 1990.
Abstract
A sorting network is a combinational circuit for sorting constructed from comparison-swap units.
The depth of such a circuit is a measure of its running time. It is known that
sorting-network verification is computationally intractable. However, it is reasonable to hypothesize
that only the fastest (that is, the shallowest) networks are likely to be fabricated. It is shown
that the verification of shallow sorting networks is also computationally intractable. Firstly, a method
for constructing asymptotically optimal single-exception sorting networks is demonstrated.
These are networks which sort all zero-one inputs except one. More specifically, their depth
is $D(n-1)+2\log (n-1)+2$, where $D(n)$ is the minimum depth of an $n$-input sorting network. It
follows that the verification problem for sorting networks of depth
$2D(n) + 6 \log n + O(1)$ is Co-NP complete. Given the current state of knowledge about $D(n)$ for large
$n$, this indicates that the complexity of verification for shallow sorting networks
is as great as for deep networks
Ian Parberry,
"A Computer Assisted Optimal Depth Lower Bound for
Nine-Input Sorting Networks".
Mathematical Systems Theory, Vol. 24, pp. 101-116, 1991.
A preliminary version of this paper appeared in the
Proceedings of Supercomputing '89, pp. 152-161, Reno, Nevada, Nov. 1989.
[pdf]
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.
Author's Comments
-
This paper had the good fortune to be mentioned on
p. 666 of the second edition of
Donald Knuth's The Art of Computer Programming,
Vol. 3, Sorting and Searching.
-
The results of this paper have since been superceded by the following:
D. Bundala, M. Codish, L. Cruz-Filipe, P. Schneider-Kamp, J. Závodný, "Optimal-depth sorting networks", Journal of Computer and System Sciences, Vol. 84, pp. 185-204, 2017.
-
The original backtracking code from the 1980s has been lost to crashed floppy disks, hard drives and magnetic tapes. However, in the interest of completeness I have recreated it from the paper and posted it to
https://github.com/Ian-Parberry/sortingnetworksearch. Documentation
can be found at
https://ian-parberry.github.io/sortingnetworksearch/.
Bruce Parker and
Ian Parberry,
"Constructing Sorting Networks from $k$-sorters",
Information Processing Letters, Vol. 33, No. 3, pp. 157-162, 1989.
[pdf]
Abstract
We study the problem of using sorters of $k$ values to form large sorting and
merging networks. For $n$ an integral power of
$k$, we show how to merge $k$ sorted vectors of length $n/k$ each using $4 \log_k n - 3$ layers
of $k$-sorters and $4 \log_k n - 5$ layers of
k-input binary mergers. As a result, we show how to sort n values
using $2 \log_k^2 n - \log_k n$ layers of $k$-sorters and
$2 \log_k^2 n - 3 \log_k n + 1$ layers of $k$-input binary mergers.
