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(log n + t) iterations of the network. Our construction requires O(log n + (log log N)(2) (log t)(3)) iterations which makes it asymptotically faster for t >> log N. (c) 2005 Elsevier B.V. All rights reserved.
comparator sorting network periodic sorting network