Generalizing bitonic and odd-even merging networks
Kathy J. Liszka · 1992
Since 1968, bitonic merging networks have been used for parallel merging networks, among other applications. Recently, improvements were made to generalize the topology of the switching elements involved. Until now, however, there has been no general method for sorting a bitonic sequence of N keys, N a prime, or N a composite that decomposes into primes larger than 3. Two solutions have been developed that generalize bitonic sorters for any N. This has also led to a link between the bitonic merger and the odd-even merge. A new sorting network, the modulo merge, is a general version of the odd-even merge, not constrained by a modulo two division. Variations on the modulo merge incorporate the general bitonic merge.