I'm looking for the most efficient sorting network for binary values. In my case, efficiency is the number of compare-and-swap operations required.
Background: Sorting networks sort a list of values using a sequence of compare-and-swap operations with rigid positions. Due to the rigid sequence, they are suitable for implementation in hardware or for parallelization. I have two sub-questions:
If I know that my data is binary, e.g. (0, 1, 1, 0, 1, 1 ...), can I construct a more efficient sorting network than for arbitrary values?
It is trivial to turn algorithms like bubble sort into a sorting network, since the algorithm is using a rigid sequence of compare-and-swap operations. Is there a systematic way to turn any sorting algorithm (e.g. this one for sorting a binary array) into a sorting network? The example algorithm uses compare-and-swap at dynamic positions (determined by two shifting indices).
(I should add that one property of sorting networks, namely that multiple compare-and-swap operations can be grouped and performed in parallel (as their index pairs are not overlapping), is not important for my application. I'm just interested in finding the shortest rigid sequence of compare-and-swap operations.)
Thanks for your help!
A sorting network for binary numbers cannot be simpler than one for arbitrary numbers, else there would indeed be a contradiction. So if a network has optimal size (known for up to 12 inputs nowadays) then the same applies for binary inputs.
"Sorting" binary numbers is in itself of course no meaningful activity: you can just count the 1's in the input vector and directly produce the output from it.