Constant-depth sorting networks.

Abstract:  Assume that you want to sort n integers, and you have many copies of a device that can sort k integers. At one step, you can partition n integers into sets of size at most k by putting them into your devices. How many such steps do you need to sort your initial array?

When k = 2, this problem is just a problem of constructing a sorting network. It can be solved in O(log n) steps, though the construction is complicated and impractical. We consider a reversed setting. Namely, we fix a number of steps and seek for the minimal k such that our problem is solvable within this number of steps with this k. We determine the minimal k for 2,3, and 4 steps.

Joint work with Natalia Dobrokhotova-Maikova and Vladimir Podolski.

Posted on Nov 8, 2022 in ACGO, Seminars