BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-71-239
       ENTRY:: November 01, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Large [g,d] sorting networks
        TYPE:: Technical Report
      AUTHOR:: Van Voorhis, David C.
        DATE:: August 1971
       PAGES:: 68
    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)$.
       NOTES:: [Adminitrivia V1/Prg/19951101]
         END:: STAN//CS-TR-71-239