Institution: Stanford University, Department of Computer Science

Title: Large [g,d] sorting networks

Author: Van Voorhis, David C.

Date: August 1971

Abstract: With only a few exceptions the minimum-comparator N-sorter networks employ the generalized "divide-sort-merge" strategy. That is, the N inputs are divided among g $\geq$ 2 smaller sorting networks -- of size $N_1,N_2,...,N_g$, where $N = \sum_{k=1}^{g} N_k$ -- that comprise the initial portion of the N-sorter network. The remainder of the N-sorter is a comparator network that merges the outputs of the $N_1-, N_2-, ...,$ and $N_g$-sorter networks into a single sorted sequence. The most economical merge networks yet designed, known as the "[g,d]" merge networks, consist of d smaller merge networks -- where d is a common divisor of $N_1,N_2,...,N_g$ -- followed by a special comparator network labeled a "[g,d] f-network." In this paper we describe special constructions for $[2^r,2^r]$ f-networks, r > 1, which enable us to reduce the number of comparators required by a large N-sorter network from $.25N {log_2 N)}^2 - .25N(log_2 N) + O(N) to .25N{(log_2 N)}^2 - .37N(log_2 N) + O(N)$.

http://i.stanford.edu/pub/cstr/reports/cs/tr/71/239/CS-TR-71-239.pdf