views:

72

answers:

1

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.)

+2  A: 

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]]
    [[1 3][2 4][5 6][1 5][2 3][4 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 3][2 4][5 6][1 5][2 6][3 4][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 3][2 4][5 6][1 6][2 5][3 4][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 3][2 5][4 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 3][2 5][4 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 3][2 5][4 6][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 3][2 5][4 6][1 4][2 6][3 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 3][2 5][4 6][1 5][2 4][3 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 3][2 5][4 6][1 6][2 4][3 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 3][2 6][4 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 3][2 6][4 5][1 2][3 5][4 6][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 3][2 6][4 5][1 4][2 3][5 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 3][2 6][4 5][1 4][2 5][3 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 3][2 6][4 5][1 5][2 4][3 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 3][2 6][4 5][1 6][2 4][3 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 3][5 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 3][5 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 4][2 3][5 6][1 3][2 5][4 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 4][2 3][5 6][1 5][2 4][3 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 4][2 3][5 6][1 5][2 6][3 4][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 4][2 3][5 6][1 6][2 5][3 4][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 4][2 5][3 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 4][2 5][3 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 5][3 6][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 4][2 5][3 6][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 5][3 6][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 5][3 6][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 6][3 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 4][2 6][3 5][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 6][3 5][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 4][2 6][3 5][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 6][3 5][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 4][2 6][3 5][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 3][4 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 5][2 3][4 6][1 2][3 6][4 5][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 5][2 3][4 6][1 3][2 4][5 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 5][2 3][4 6][1 4][2 5][3 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 3][4 6][1 4][2 6][3 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 3][4 6][1 6][2 4][3 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 4][3 6][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 5][2 4][3 6][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 4][3 6][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 4][3 6][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 4][3 6][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 5][2 4][3 6][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 6][3 4][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 6][3 4][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 6][3 4][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 5][2 6][3 4][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 5][2 6][3 4][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 5][2 6][3 4][1 6][2 3][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 3][4 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 6][2 3][4 5][1 2][3 5][4 6][1 4][2 3][5 6][2 4][3 5][3 4]]
    [[1 6][2 3][4 5][1 3][2 4][5 6][1 2][3 6][4 5][2 4][3 5][3 4]]
    [[1 6][2 3][4 5][1 4][2 5][3 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 3][4 5][1 4][2 6][3 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 3][4 5][1 5][2 4][3 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 4][3 5][1 2][3 4][5 6][1 3][2 5][4 6][2 3][4 5][3 4]]
    [[1 6][2 4][3 5][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 4][3 5][1 3][2 5][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 4][3 5][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 4][3 5][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 6][2 4][3 5][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 5][3 4][1 2][3 5][4 6][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 5][3 4][1 2][3 6][4 5][1 3][2 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 5][3 4][1 3][2 4][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 6][2 5][3 4][1 3][2 6][4 5][1 2][3 4][5 6][2 3][4 5][3 4]]
    [[1 6][2 5][3 4][1 4][2 3][5 6][1 2][3 5][4 6][2 3][4 5][3 4]]
    [[1 6][2 5][3 4][1 5][2 3][4 6][1 2][3 4][5 6][2 3][4 5][3 4]] 

Personally I'd check that the sorting network is correct before using it, rather than taking the word of some random page on the internet. Brute force "only" requires running it against n! inputs.

All of the optimal 5-networks involve "3" in the last swap, so picking the median in fewer swaps isn't quite so easy as all that. It can be done in 6 comparisons, though. There's way more code than you need here, if you can ignore the whining about the question:

http://stackoverflow.com/questions/480960/code-to-calculate-median-of-five-in-c

To pick a median you don't necessarily do any swaps, other than perhaps one unconditional swap if you want to preserve all 5 values. A move might be adequate.

CW, in case anyone feels strongly that SO needs a copy-and-paste of the complete list of minimal sorting networks for small n.

Steve Jessop
Thanks for the link! I don't know if SO needs a copy-and-paste of it, but it would sure be nice to improve the pagerank of that reference, since it didn't turn up at all in my standard googling. :-(
R..
Yes, SO needs a copy-and-paste.
Amigable Clark Kant
@Amigable Clark Kant: +100 to your comment if I could give it. Try the link now... Anyone have a cached copy to paste here?
R..
@Registered User, make it so.
Amigable Clark Kant