c - Standard sorting networks for small values of n

Question

I'm looking for a sorting network implementation of a 5-element sort, but since I couldn't find a good reference on SO, I'd like to ask for sorting networks for all small values of n, at least n=3 through n=6 but higher values would be great too. A good answer should at least list them as sequences of "swap" (sort on 2 elements) operations, but it might also be nice to see the recursive decomposition in terms of lower-order sorting networks.

For my application, I actually only care about the median of 5 elements, not actually putting them in order. That is, the order of the other 4 elements may be unspecified in the result as long as the median ends up in the right place. Can a sorting-networks-related approach be used to compute the median with fewer swaps than performing a full sort? If so, such a solution to my problem (for n=5) and for other cases would make a great answer too.

(Note: I've tagged this question C because C is the language I use and I suspect people who follow the C tag have good answers, but I don't really care if an answer is actually written in C versus pseudo-code as long as it easily translates to C, which it should naturally do as long as the above-mentioned criteria are met.)

Answer 1

Pick one from each section, presumably whichever runs fastest on your hardware since we're firmly in the realm of "fiendish optimization": http://smarterrecall.com/networks.html , reproduced below:

I created this site to list all possible optimal sorting networks up to 6-inputs written using a program in matlab. The longest run-time is for 5-inputs at 45 seconds. If you are interested in contacting me, I can be reached at rpl1 [AT] rice [DOT] edu Cheers, Richard L.

----------

 - 2-input: 1 network

    [[1 2]]


----------


 - 3-input: 6 networks

[[1 2][1 3][2 3]]
[[1 2][2 3][1 2]]
[[1 3][1 2][2 3]]
[[1 3][2 3][1 2]]
[[2 3][1 2][2 3]]
[[2 3][1 3][1 2]]


----------

 - 4-input: 3 networks

[[1 2][3 4][1 3][2 4][2 3]]
[[1 3][2 4][1 2][3 4][2 3]]
[[1 4][2 3][1 2][3 4][2 3]]


----------

 - 5-input: 180 networks

    [[1 2][3 4][1 3][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 2][3 4][1 3][2 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 2][3 4][1 3][4 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 2][3 4][1 3][4 5][2 5][3 4][1 3][2 4][2 3]]
    [[1 2][3 4][1 4][2 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 2][3 4][1 4][3 5][1 3][2 5][2 3][4 5][3 4]]
    [[1 2][3 4][1 5][2 3][1 2][4 5][2 4][3 5][3 4]]
    [[1 2][3 4][1 5][2 4][1 3][2 5][2 3][4 5][3 4]]
    [[1 2][3 4][1 5][2 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 2][3 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 2][3 4][2 4][3 5][1 2][4 5][1 3][2 4][2 3]]
    [[1 2][3 4][2 4][3 5][1 3][2 5][2 3][4 5][3 4]]
    [[1 2][3 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 2][3 5][1 3][2 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 2][3 5][1 3][4 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 2][3 5][1 3][4 5][2 5][3 4][1 3][2 4][2 3]]
    [[1 2][3 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]]
    [[1 2][3 5][1 4][2 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 2][3 5][1 4][2 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 2][3 5][1 5][2 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 2][3 5][1 5][3 4][1 3][2 4][2 3][4 5][3 4]]
    [[1 2][3 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 2][3 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]]
    [[1 2][3 5][2 5][3 4][1 3][2 4][2 3][4 5][3 4]]
    [[1 2][4 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 2][4 5][1 3][2 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 2][4 5][1 3][2 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 2][4 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]]
    [[1 2][4 5][1 4][2 3][2 4][3 5][1 2][3 4][2 3]]
    [[1 2][4 5][1 4][3 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 2][4 5][1 4][3 5][2 5][3 4][1 3][2 4][2 3]]
    [[1 2][4 5][1 5][2 3][2 4][3 5][1 2][3 4][2 3]]
    [[1 2][4 5][1 5][3 4][1 3][2 4][2 3][4 5][3 4]]
    [[1 2][4 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]]
    [[1 2][4 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]]
    [[1 2][4 5][2 5][3 4][1 3][2 4][2 3][4 5][3 4]]
    [[1 3][2 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 3][2 4][1 2][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 3][2 4][1 2][4 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 3][2 4][1 2][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 3][2 4][1 4][2 5][1 2][3 5][2 3][4 5][3 4]]
    [[1 3][2 4][1 4][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 3][2 4][1 5][2 3][1 2][4 5][2 4][3 5][3 4]]
    [[1 3][2 4][1 5][3 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 3][2 4][1 5][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 3][2 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 3][2 4][2 5][3 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 3][2 4][2 5][3 4][1 3][4 5][1 2][3 4][2 3]]
    [[1 3][2 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[1 3][2 5][1 2][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 3][2 5][1 2][4 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 3][2 5][1 2][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 3][2 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]]
    [[1 3][2 5][1 4][3 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 3][2 5][1 4][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 3][2 5][1 5][2 4][1 2][3 4][2 3][4 5][3 4]]
    [[1 3][2 5][1 5][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 3][2 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 3][2 5][2 4][3 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 3][2 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]]
    [[1 3][4 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[1 3][4 5][1 2][3 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 3][4 5][1 2][3 5][2 5][3 4][1 3][2 4][2 3]]
    [[1 3][4 5][1 4][2 3][1 2][4 5][2 4][3 5][3 4]]
    [[1 3][4 5][1 4][2 3][2 4][3 5][1 2][3 4][2 3]]
    [[1 3][4 5][1 4][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 3][4 5][1 4][2 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 3][4 5][1 5][2 3][2 4][3 5][1 2][3 4][2 3]]
    [[1 3][4 5][1 5][2 4][1 2][3 4][2 3][4 5][3 4]]
    [[1 3][4 5][2 4][3 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 3][4 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]]
    [[1 3][4 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]]
    [[1 4][2 3][1 2][3 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 4][2 3][1 2][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][2 3][1 2][4 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 4][2 3][1 2][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 4][2 3][1 3][2 5][1 2][4 5][2 4][3 5][3 4]]
    [[1 4][2 3][1 3][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 4][2 3][1 5][2 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 4][2 3][1 5][3 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 4][2 3][1 5][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][2 3][2 4][3 5][1 3][4 5][1 2][3 4][2 3]]
    [[1 4][2 3][2 5][3 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 4][2 3][2 5][3 4][1 3][4 5][1 2][3 4][2 3]]
    [[1 4][2 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[1 4][2 5][1 2][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][2 5][1 2][3 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 4][2 5][1 2][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][2 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 4][2 5][1 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 4][2 5][1 3][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 4][2 5][1 5][2 3][1 2][3 4][2 3][4 5][3 4]]
    [[1 4][2 5][1 5][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][2 5][2 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 4][2 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 4][2 5][2 4][3 5][1 3][4 5][1 2][3 4][2 3]]
    [[1 4][3 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[1 4][3 5][1 2][4 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 4][3 5][1 2][4 5][2 5][3 4][1 3][2 4][2 3]]
    [[1 4][3 5][1 3][2 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 4][3 5][1 3][2 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][3 5][1 3][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 4][3 5][1 3][2 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][3 5][1 5][2 3][1 2][3 4][2 3][4 5][3 4]]
    [[1 4][3 5][1 5][2 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 4][3 5][2 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 4][3 5][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 4][3 5][2 5][3 4][1 2][4 5][1 3][2 4][2 3]]
    [[1 5][2 3][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[1 5][2 3][1 2][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][2 3][1 2][4 5][1 4][2 3][2 4][3 5][3 4]]
    [[1 5][2 3][1 2][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 5][2 3][1 3][2 4][1 2][4 5][2 4][3 5][3 4]]
    [[1 5][2 3][1 3][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 5][2 3][1 4][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][2 3][1 4][3 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][2 3][1 4][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][2 3][2 4][3 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][2 3][2 4][3 5][1 3][4 5][1 2][3 4][2 3]]
    [[1 5][2 3][2 5][3 4][1 3][4 5][1 2][3 4][2 3]]
    [[1 5][2 4][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[1 5][2 4][1 2][3 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][2 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 5][2 4][1 2][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][2 4][1 3][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][2 4][1 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][2 4][1 3][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[1 5][2 4][1 4][2 3][1 2][3 5][2 3][4 5][3 4]]
    [[1 5][2 4][1 4][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][2 4][2 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][2 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 5][2 4][2 5][3 4][1 3][4 5][1 2][3 4][2 3]]
    [[1 5][3 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 5][3 4][1 2][4 5][1 3][2 4][2 3][4 5][3 4]]
    [[1 5][3 4][1 2][4 5][2 5][3 4][1 3][2 4][2 3]]
    [[1 5][3 4][1 3][2 4][1 2][3 5][2 3][4 5][3 4]]
    [[1 5][3 4][1 3][2 4][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][3 4][1 3][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][3 4][1 3][2 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][3 4][1 4][2 3][1 2][3 5][2 3][4 5][3 4]]
    [[1 5][3 4][1 4][2 5][2 3][4 5][1 2][3 4][2 3]]
    [[1 5][3 4][2 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[1 5][3 4][2 3][4 5][1 4][3 5][1 2][3 4][2 3]]
    [[1 5][3 4][2 4][3 5][1 2][4 5][1 3][2 4][2 3]]
    [[2 3][4 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[2 3][4 5][1 2][3 5][1 4][2 3][2 4][3 5][3 4]]
    [[2 3][4 5][1 2][3 5][2 5][3 4][1 3][2 4][2 3]]
    [[2 3][4 5][1 3][2 4][1 2][4 5][2 4][3 5][3 4]]
    [[2 3][4 5][1 3][2 4][1 4][3 5][1 2][3 4][2 3]]
    [[2 3][4 5][1 3][2 5][1 4][3 5][1 2][3 4][2 3]]
    [[2 3][4 5][1 4][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[2 3][4 5][1 4][3 5][1 2][3 4][2 3][4 5][3 4]]
    [[2 3][4 5][1 4][3 5][2 3][4 5][1 2][3 4][2 3]]
    [[2 3][4 5][1 5][2 4][1 2][3 4][2 3][4 5][3 4]]
    [[2 3][4 5][1 5][2 4][1 4][3 5][1 2][3 4][2 3]]
    [[2 3][4 5][1 5][3 4][1 2][4 5][1 3][2 4][2 3]]
    [[2 4][3 5][1 2][3 4][1 3][2 5][2 3][4 5][3 4]]
    [[2 4][3 5][1 2][4 5][1 3][2 4][2 3][4 5][3 4]]
    [[2 4][3 5][1 2][4 5][2 5][3 4][1 3][2 4][2 3]]
    [[2 4][3 5][1 3][2 5][1 2][3 4][2 3][4 5][3 4]]
    [[2 4][3 5][1 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[2 4][3 5][1 3][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[2 4][3 5][1 4][2 3][1 2][3 5][2 3][4 5][3 4]]
    [[2 4][3 5][1 4][2 3][1 3][4 5][1 2][3 4][2 3]]
    [[2 4][3 5][1 4][2 5][1 3][4 5][1 2][3 4][2 3]]
    [[2 4][3 5][1 5][2 3][1 2][3 4][2 3][4 5][3 4]]
    [[2 4][3 5][1 5][2 3][1 3][4 5][1 2][3 4][2 3]]
    [[2 4][3 5][1 5][3 4][1 2][4 5][1 3][2 4][2 3]]
    [[2 5][3 4][1 2][3 5][1 3][2 4][2 3][4 5][3 4]]
    [[2 5][3 4][1 2][4 5][1 3][2 4][2 3][4 5][3 4]]
    [[2 5][3 4][1 2][4 5][2 5][3 4][1 3][2 4][2 3]]
    [[2 5][3 4][1 3][2 4][1 2][3 5][2 3][4 5][3 4]]
    [[2 5][3 4][1 3][4 5][1 2][3 4][2 3][4 5][3 4]]
    [[2 5][3 4][1 3][4 5][2 4][3 5][1 2][3 4][2 3]]
    [[2 5][3 4][1 4][2 3][1 2][3 5][2 3][4 5][3 4]]
    [[2 5][3 4][1 4][2 3][1 3][4 5][1 2][3 4][2 3]]
    [[2 5][3 4][1 4][3 5][1 2][4 5][1 3][2 4][2 3]]
    [[2 5][3 4][1 5][2 3][1 2][3 4][2 3][4 5][3 4]]
    [[2 5][3 4][1 5][2 3][1 3][4 5][1 2][3 4][2 3]]
    [[2 5][3 4][1 5][2 4][1 3][4 5][1 2][3 4][2 3]]


----------


 - 6-input: 90 networks

    [[1 2][3 4][5 6][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 2][3 4][5 6][1 3][2 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 2][3 4][5 6][1 4][2 6][3 5][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 2][3 4][5 6][1 5][2 3][4 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 2][3 4][5 6][1 5][2 4][3 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 2][3 4][5 6][1 6][2 4][3 5][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 2][3 5][4 6][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 2][3 5][4 6][1 3][2 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 2][3 5][4 6][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 2][3 5][4 6][1 4][2 5][3 6][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 2][3 5][4 6][1 5][2 6][3 4][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 2][3 5][4 6][1 6][2 5][3 4][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 2][3 6][4 5][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 2][3 6][4 5][1 3][2 5][4 6][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 2][3 6][4 5][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 2][3 6][4 5][1 4][2 6][3 5][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 2][3 6][4 5][1 5][2 6][3 4][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 2][3 6][4 5][1 6][2 5][3 4][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 3][2 4][5 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 3][2 4][5 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 3][2 4][5 6][1 4][2 5][3 6][1 2][3 5][4 6][2 3][4 5][3 4]]