# Sorting Networks

*k*-sorters (1989)

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.

# 9-Input Sorting Networks (1989, 1991)

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 Comment

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 Pairwise Sorting Network (1992)

Ian Parberry,
"The Pairwise Sorting Network".
*Parallel Processing Letters*, Vol. 2, No. 2,3, pp. 205-211, 1992.
[pdf]

### 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.

### Author's Comment

A

2010 paper by Michael Codish and Moshe Zazon-Ivry
quotes my paper as saying:
"It is the first sorting network to be competitive with the odd-even sort
for all values of n. The value of the pairwise sorting network is not that
it is superior to the odd-even sorting network in any sense, but that it
is the first serious rival to appear in over 20 years",
and they go on to say:
"In this paper, almost 20 years after the introduction of pairwise sorting networks, we are in the position to state that pairwise
sorting networks are significantly superior to odd-even sorting networks, at least for encoding cardinality
constraints."
Very cool.

# Sorting Network Verification (1990)

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)+2log(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

# Sorting Network Verification Reloaded (1991)

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.

Created April 21, 2010.
Written in HTML 4.01 and CSS 3 using vi.
Last updated August 2, 2011.