Fast periodic correction networks

We consider the problem of sorting N-element inputs differing from already sorted sequences by t small changes. To perform this task we construct a constant depth comparator network that is applied periodically. The two constructions for this problem made by previous authors required O(logn+t) iterations of the network. Our construction requires iterations which makes it asymptotically faster for t⪢logN.