There are simple algorithms to construct sorting networks from 2-sorters, e.g. Batcher's bitonic sorters and Pairwise sorting networks.

How can one construct general sorters with a low number of $k$-sorters, $k\gt 2$?
Is there a similar result for select / partial sorting, say, the $\sqrt n$th element or the top $\sqrt n$ ones?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.