Faster merging networks with a small constant period

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). In our previous paper Faster 3-Periodic Merging Network   we reduced the time of merging on 3-periodic networks by a factor of 2, i.e. from 12log⁡N12log⁡N to 6log⁡N6log⁡N, compared to the first construction given by Kutyłowski, Loryś and Oesterdiekhoff. Note that merging on 2-periodic networks requires linear time. In this paper we extend our construction, and the analysis from that paper to any period p≥3p≥3. For p≥3p≥3 our p  -periodic network merges two sorted sequences of length N/2N/2 in at most 2pp−2log⁡N+pp−8p−2 rounds. The previous bound given by Kutyłowski et al. was 2.25pp−2.42log⁡N for p≥4p≥4. That means, for example, that our 4-periodic merging networks work in time upper-bounded by 4log⁡N4log⁡N and our 6-periodic ones in time upper-bounded by 3log⁡N3log⁡N compared to the corresponding 5.67log⁡N5.67log⁡N and 3.8log⁡N3.8log⁡N previous bounds. Our construction is regular in the sense that it is parametrised with p   and one can set p=3p=3 to get the family of 3-periodic merging networks, whereas the previous constructions given for p=3p=3 and p≥4p≥4 differ in their structures. Moreover, our networks are also periodic sorters, and tests on random permutations suggest that the average sorting time might be close to log2⁡Nlog2⁡N.