A Generalized Bitonic Sorting Network

Abstract

The bitonic sorting network will sort N-2^m keys in O(log^2N) time with 0(Nlog^2N) comparators. Developments on the sorter enable the network to sort N-pq keys, a composite number. 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. The oddmerge method removes this constraint while maintaining the same cost and delay, using a uniform and efficient decomposition.