Brief Announcement: Faster 3-Periodic Merging Networks

We consider the problem of merging two sorted sequences on a comparator network that is used repeatedly, that is, if the output is not sorted, the network is applied again using the output as input. The challenging task is to construct such networks of small depth (called a period in this context). The first constructions of merging networks with a constant period were described by Kutylowski et al. They gave 3-periodic network that merges two sorted sequences of N numbers in time 12 log N and a similar network of period 4 that works in 5.67 log N. We present a new family of 3-periodic merging networks with merging time upper-bounded by 6 log N. The construction can be easily generalized to larger constant periods with decreasing running time, for example, to 4-periodic ones that work in time upper-bounded by 4 log N