PERIODIC MERGING NETWORKS

We consider the problem of merging two sorted sequences on constant de gree networks performing compare-exchange operations only. The classic al solution to this problem is given by the networks based on Batcher' s Odd-Even Merge and Bitonic Merge running in log(2n) time. Due to the obvious log n lower bound for the runtime, this is time-optimal, We p resent a new family of merging networks working in a completely differ ent way than the previously known algorithms. They have a novel proper ty of being periodic: this means that for some (small) constant k, eac h processing unit of the network performs the same operations at steps t and t + k (as long as t + k does not exceed the runtime). The only operations executed are compare-ex;change operations, just like in the case of Batcher's networks, The architecture of the networks is very simple and easy to lay out. We show that even for period 3 there is a network in our family merging two n-element sorted sequences in time O (log n). Since each network of period 2 requires Theta(n) steps to me rge such sequences, 3 is the smallest period for which we may achieve a fast runtime.