Smallest and fastest sorting networks for a given number of inputs

Below are the best performing sorting networks known by the author for network sizes of up to 32 inputs, in terms of two metrics:

Provided is a minimum set of networks that each can be the best choice depending on how both criteria are weighted.

If no source is mentioned, the network was generated by the SorterHunter program, which in many cases matches or outperforms pre-existing networks.

For a number of input sizes (n), the used method was able to reduce the upper bound for the minimal network size S(n) compared to the results reported by V. Valsalam & R. Miikkulainen [VM13].
This was the case for 18…23 inputs. For 24…29, 33…48 and 54…56 inputs, a reduction was achieved vs. the Batcher odd-even and Van Voorhis (4,4) merges of smaller networks.

For 25 and 26 inputs, a reduction in depth was achieved vs. the Batcher odd-even merge of smaller networks, lowering the optimal depth upper bound to 13 layers. For 34 inputs, a similar reduction in depth to 15 layers was achieved, and for 42…44 inputs a reduction to 17 layers.

For questions, remarks, or to contribute improved results please contact bert.o.dobbelaere[at]telenet[dot]be.

For a version of this page covering larger input counts, see the extended list of sorting networks

Summary table

Number of inputs(Size,Depth) combinationsMin. size bounds
OEIS A003075		Min. depth bounds
OEIS A067782		Comments
2(1, 1)   11Trivial
3(3, 3)   33[TAOCPv3]
4(5, 3)   53[TAOCPv3]
5(9, 5)   95[TAOCPv3]
6(12, 5)   125[TAOCPv3]
7(16, 6)   166[TAOCPv3]
8(19, 6)   196[TAOCPv3]
9(25, 7)   257[TAOCPv3], Optimal depth proven in [Par89], optimal size proven in [CCFS16]
10(29, 8)   (31, 7)   297[TAOCPv3], Optimal depth proven in [Par89], optimal size proven in [CCFS16]
11(35, 8)   358[TAOCPv3], Optimal depth proven in [BZ14], optimal size proven by [Harder19]
12(39, 9)   (40, 8)   398[TAOCPv3], Optimal depth proven in [BZ14], optimal size proven by [Harder19]
13(45, 10)   (46, 9)   43…459[TAOCPv3], Optimal depth proven in [BZ14]
14(51, 10)   (52, 9)   47…519[TAOCPv3], Optimal depth proven in [BZ14]
15(56, 10)   (57, 9)   51…569[TAOCPv3], Optimal depth proven in [BZ14]
16(60, 10)   (61, 9)   55…609[TAOCPv3], Optimal depth proven in [BZ14]
17(71, 12)   (72, 11)   (74, 10)   60…7110Size ubound: [Baddar09], depth ubound: [EM14], depth optimality: [CCEMS16]
18(77, 12)   (78, 11)   65…7710…11Size ubound: SorterHunter, depth ubound: [Baddar09]
19(85, 12)   (87, 11)   70…8510…11Size ubound: SorterHunter, depth ubound: [EM14].
20(91, 12)   (93, 11)   75…9110…11Size ubound: SorterHunter, depth ubound: [EM14].
21(99, 15)   (100, 12)   80…9910…12Size ubound: SorterHunter, depth ubound: [Baddar09]
22(106, 13)   (107, 12)   85…10610…12Size ubound: SorterHunter, depth ubound: [Baddar09]
23(114, 14)   (115, 13)   (116, 12)   90…11410…12Size ubound: SorterHunter, depth ubound: [Ehlers17]
24(120, 13)   (122, 12)   95…12010…12Size ubound: SorterHunter, depth ubound: [Ehlers17]
25(130, 15)   (131, 13)   100…13010…13Depth ubound: SorterHunter. Size ubound: SorterHunter
26(139, 14)   (141, 13)   105…13910…13Depth ubound: SorterHunter. Size ubound: SorterHunter
27(147, 16)   (148, 14)   110…14710…14Depth ubound: odd-even merge. Size ubound: SorterHunter
28(155, 14)   115…15510…14Depth ubound: odd-even merge. Size ubound: SorterHunter
29(164, 15)   (166, 14)   120…16410…14Depth ubound: odd-even merge. Size ubound: SorterHunter
30(172, 14)   125…17210…14Size/depth ubounds: Batcher odd-even merge
31(180, 14)   130…18010…14Size/depth ubounds: Batcher odd-even merge
32(185, 14)   135…18510…14Size/depth ubounds: Batcher odd-even merge

Individual networks:

Sorting network for 2 inputs, 1 CE, 1 layer:

[(0,1)]

Trivial sorting network for two inputs. The only simpler "network" is the one for one input, which uses no CE at all and is represented by a horizontal line.		 Auto generated
Sorting network for 3 inputs, 3 CEs, 3 layers:

[(0,2)]
[(0,1)]
[(1,2)]

 Auto generated
Sorting network for 4 inputs, 5 CEs, 3 layers:

[(0,2),(1,3)]
[(0,1),(2,3)]
[(1,2)]

 Auto generated
Sorting network for 5 inputs, 9 CEs, 5 layers:

[(0,3),(1,4)]
[(0,2),(1,3)]
[(0,1),(2,4)]
[(1,2),(3,4)]
[(2,3)]

 Auto generated
Sorting network for 6 inputs, 12 CEs, 5 layers:

[(0,5),(1,3),(2,4)]
[(1,2),(3,4)]
[(0,3),(2,5)]
[(0,1),(2,3),(4,5)]
[(1,2),(3,4)]

 Auto generated
Sorting network for 7 inputs, 16 CEs, 6 layers:

[(0,6),(2,3),(4,5)]
[(0,2),(1,4),(3,6)]
[(0,1),(2,5),(3,4)]
[(1,2),(4,6)]
[(2,3),(4,5)]
[(1,2),(3,4),(5,6)]

 Auto generated
Sorting network for 8 inputs, 19 CEs, 6 layers:

[(0,2),(1,3),(4,6),(5,7)]
[(0,4),(1,5),(2,6),(3,7)]
[(0,1),(2,3),(4,5),(6,7)]
[(2,4),(3,5)]
[(1,4),(3,6)]
[(1,2),(3,4),(5,6)]

 Auto generated
Sorting network for 9 inputs, 25 CEs, 7 layers:

[(0,3),(1,7),(2,5),(4,8)]
[(0,7),(2,4),(3,8),(5,6)]
[(0,2),(1,3),(4,5),(7,8)]
[(1,4),(3,6),(5,7)]
[(0,1),(2,4),(3,5),(6,8)]
[(2,3),(4,5),(6,7)]
[(1,2),(3,4),(5,6)]

 Auto generated
Sorting network for 10 inputs, 29 CEs, 8 layers:

[(0,8),(1,9),(2,7),(3,5),(4,6)]
[(0,2),(1,4),(5,8),(7,9)]
[(0,3),(2,4),(5,7),(6,9)]
[(0,1),(3,6),(8,9)]
[(1,5),(2,3),(4,8),(6,7)]
[(1,2),(3,5),(4,6),(7,8)]
[(2,3),(4,5),(6,7)]
[(3,4),(5,6)]

 Auto generated
Sorting network for 10 inputs, 31 CEs, 7 layers:

[(0,1),(2,5),(3,6),(4,7),(8,9)]
[(0,6),(1,8),(2,4),(3,9),(5,7)]
[(0,2),(1,3),(4,5),(6,8),(7,9)]
[(0,1),(2,7),(3,5),(4,6),(8,9)]
[(1,2),(3,4),(5,6),(7,8)]
[(1,3),(2,4),(5,7),(6,8)]
[(2,3),(4,5),(6,7)]

31 is the optimal size for 7 layers [Fon18]		 Auto generated
Sorting network for 11 inputs, 35 CEs, 8 layers:

[(0,9),(1,6),(2,4),(3,7),(5,8)]
[(0,1),(3,5),(4,10),(6,9),(7,8)]
[(1,3),(2,5),(4,7),(8,10)]
[(0,4),(1,2),(3,7),(5,9),(6,8)]
[(0,1),(2,6),(4,5),(7,8),(9,10)]
[(2,4),(3,6),(5,7),(8,9)]
[(1,2),(3,4),(5,6),(7,8)]
[(2,3),(4,5),(6,7)]

35 is the optimal size [Harder19] (see also [Fon18] for 8 or 9 layers).		 Auto generated
Sorting network for 12 inputs, 39 CEs, 9 layers:

[(0,8),(1,7),(2,6),(3,11),(4,10),(5,9)]
[(0,1),(2,5),(3,4),(6,9),(7,8),(10,11)]
[(0,2),(1,6),(5,10),(9,11)]
[(0,3),(1,2),(4,6),(5,7),(8,11),(9,10)]
[(1,4),(3,5),(6,8),(7,10)]
[(1,3),(2,5),(6,9),(8,10)]
[(2,3),(4,5),(6,7),(8,9)]
[(4,6),(5,7)]
[(3,4),(5,6),(7,8)]

39 is the optimal size [Harder19] (see also [Fon18] for 9 layers).		 Auto generated
Sorting network for 12 inputs, 40 CEs, 8 layers:

[(0,8),(1,7),(2,6),(3,11),(4,10),(5,9)]
[(0,2),(1,4),(3,5),(6,8),(7,10),(9,11)]
[(0,1),(2,9),(4,7),(5,6),(10,11)]
[(1,3),(2,7),(4,9),(8,10)]
[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11)]
[(1,2),(3,5),(6,8),(9,10)]
[(2,4),(3,6),(5,8),(7,9)]
[(1,2),(3,4),(5,6),(7,8),(9,10)]

40 is the optimal size for 8 layers [Fon18].		 Auto generated
Sorting network for 13 inputs, 45 CEs, 10 layers:

[(0,12),(1,10),(2,9),(3,7),(5,11),(6,8)]
[(1,6),(2,3),(4,11),(7,9),(8,10)]
[(0,4),(1,2),(3,6),(7,8),(9,10),(11,12)]
[(4,6),(5,9),(8,11),(10,12)]
[(0,5),(3,8),(4,7),(6,11),(9,10)]
[(0,1),(2,5),(6,9),(7,8),(10,11)]
[(1,3),(2,4),(5,6),(9,10)]
[(1,2),(3,4),(5,7),(6,8)]
[(2,3),(4,5),(6,7),(8,9)]
[(3,4),(5,6)]

 Auto generated
Sorting network for 13 inputs, 46 CEs, 9 layers:

[(0,11),(1,7),(2,4),(3,5),(8,9),(10,12)]
[(0,2),(3,6),(4,12),(5,7),(8,10)]
[(0,8),(1,3),(2,5),(4,9),(6,11),(7,12)]
[(0,1),(2,10),(3,8),(4,6),(9,11)]
[(1,3),(2,4),(5,10),(6,8),(7,9),(11,12)]
[(1,2),(3,4),(5,8),(6,9),(7,10)]
[(2,3),(4,7),(5,6),(8,11),(9,10)]
[(4,5),(6,7),(8,9),(10,11)]
[(3,4),(5,6),(7,8),(9,10)]

 Auto generated
Sorting network for 14 inputs, 51 CEs, 10 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13)]
[(0,2),(1,3),(4,8),(5,9),(10,12),(11,13)]
[(0,4),(1,2),(3,7),(5,8),(6,10),(9,13),(11,12)]
[(0,6),(1,5),(3,9),(4,10),(7,13),(8,12)]
[(2,10),(3,11),(4,6),(7,9)]
[(1,3),(2,8),(5,11),(6,7),(10,12)]
[(1,4),(2,6),(3,5),(7,11),(8,10),(9,12)]
[(2,4),(3,6),(5,8),(7,10),(9,11)]
[(3,4),(5,6),(7,8),(9,10)]
[(6,7)]

Front-concentrated, only single element in last layer		 Auto generated
Sorting network for 14 inputs, 52 CEs, 9 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13)]
[(0,2),(1,3),(4,8),(5,9),(10,12),(11,13)]
[(0,10),(1,6),(2,11),(3,13),(5,8),(7,12)]
[(1,4),(2,8),(3,6),(5,11),(7,10),(9,12)]
[(0,1),(3,9),(4,10),(5,7),(6,8),(12,13)]
[(1,5),(2,4),(3,7),(6,10),(8,12),(9,11)]
[(1,2),(3,5),(4,6),(7,9),(8,10),(11,12)]
[(2,3),(4,5),(6,7),(8,9),(10,11)]
[(3,4),(5,6),(7,8),(9,10)]

Symmetric variant replacing asymmetric predecessor, was surprisingly hard to find using SorterHunter.		 Auto generated
Sorting network for 15 inputs, 56 CEs, 10 layers:

[(1,2),(3,10),(4,14),(5,8),(6,13),(7,12),(9,11)]
[(0,14),(1,5),(2,8),(3,7),(6,9),(10,12),(11,13)]
[(0,7),(1,6),(2,9),(4,10),(5,11),(8,13),(12,14)]
[(0,6),(2,4),(3,5),(7,11),(8,10),(9,12),(13,14)]
[(0,3),(1,2),(4,7),(5,9),(6,8),(10,11),(12,13)]
[(0,1),(2,3),(4,6),(7,9),(10,12),(11,13)]
[(1,2),(3,5),(8,10),(11,12)]
[(3,4),(5,6),(7,8),(9,10)]
[(2,3),(4,5),(6,7),(8,9),(10,11)]
[(5,6),(7,8)]

 Auto generated
Sorting network for 15 inputs, 57 CEs, 9 layers:

[(0,6),(1,10),(2,14),(3,9),(4,12),(5,13),(7,11)]
[(0,7),(2,5),(3,4),(6,11),(8,10),(9,12),(13,14)]
[(1,13),(2,3),(4,6),(5,9),(7,8),(10,14),(11,12)]
[(0,3),(1,4),(5,7),(6,13),(8,9),(10,11),(12,14)]
[(0,2),(1,5),(3,8),(4,6),(7,10),(9,11),(12,13)]
[(0,1),(2,5),(3,10),(4,8),(6,7),(9,12),(11,13)]
[(1,2),(3,4),(5,6),(7,9),(8,10),(11,12)]
[(3,5),(4,6),(7,8),(9,10)]
[(2,3),(4,5),(6,7),(8,9),(10,11)]

 Auto generated
Sorting network for 16 inputs, 60 CEs, 10 layers:

[(0,13),(1,12),(2,15),(3,14),(4,8),(5,6),(7,11),(9,10)]
[(0,5),(1,7),(2,9),(3,4),(6,13),(8,14),(10,15),(11,12)]
[(0,1),(2,3),(4,5),(6,8),(7,9),(10,11),(12,13),(14,15)]
[(0,2),(1,3),(4,10),(5,11),(6,7),(8,9),(12,14),(13,15)]
[(1,2),(3,12),(4,6),(5,7),(8,10),(9,11),(13,14)]
[(1,4),(2,6),(5,8),(7,10),(9,13),(11,14)]
[(2,4),(3,6),(9,12),(11,13)]
[(3,5),(6,8),(7,9),(10,12)]
[(3,4),(5,6),(7,8),(9,10),(11,12)]
[(6,7),(8,9)]

Size and depth match the handcrafted network of M.W. Green, 1969 [TAOCPv3]. It is remarkable that the last three layers (found by independent computer search) are identical to those in Green's network.		 Auto generated
Sorting network for 16 inputs, 61 CEs, 9 layers:

[(0,5),(1,4),(2,12),(3,13),(6,7),(8,9),(10,15),(11,14)]
[(0,2),(1,10),(3,6),(4,7),(5,14),(8,11),(9,12),(13,15)]
[(0,8),(1,3),(2,11),(4,13),(5,9),(6,10),(7,15),(12,14)]
[(0,1),(2,4),(3,8),(5,6),(7,12),(9,10),(11,13),(14,15)]
[(1,3),(2,5),(4,8),(6,9),(7,11),(10,13),(12,14)]
[(1,2),(3,5),(4,11),(6,8),(7,9),(10,12),(13,14)]
[(2,3),(4,5),(6,7),(8,9),(10,11),(12,13)]
[(4,6),(5,7),(8,10),(9,11)]
[(3,4),(5,6),(7,8),(9,10),(11,12)]

 Auto generated
Sorting network for 17 inputs, 71 CEs, 12 layers:

[(0,11),(1,15),(2,10),(3,5),(4,6),(8,12),(9,16),(13,14)]
[(0,6),(1,13),(2,8),(4,14),(5,15),(7,11)]
[(0,8),(3,7),(4,9),(6,16),(10,11),(12,14)]
[(0,2),(1,4),(5,6),(7,13),(8,9),(10,12),(11,14),(15,16)]
[(0,3),(2,5),(6,11),(7,10),(9,13),(12,15),(14,16)]
[(0,1),(3,4),(5,10),(6,9),(7,8),(11,15),(13,14)]
[(1,2),(3,7),(4,8),(6,12),(11,13),(14,15)]
[(1,3),(2,7),(4,5),(9,11),(10,12),(13,14)]
[(2,3),(4,6),(5,7),(8,10)]
[(3,4),(6,8),(7,9),(10,12)]
[(5,6),(7,8),(9,10),(11,12)]
[(4,5),(6,7),(8,9),(10,11),(12,13)]

Size matches result from Valsalam & Miikkulainen [VM13]. Depth reduced from 17 to 12.		 Auto generated
Sorting network for 17 inputs, 72 CEs, 11 layers:

[(0,8),(1,3),(2,6),(4,15),(5,13),(9,16),(10,11),(12,14)]
[(0,2),(1,4),(3,15),(5,8),(6,14),(7,9),(13,16)]
[(2,13),(3,11),(5,10),(6,9),(7,12),(8,15),(14,16)]
[(0,7),(1,5),(3,6),(4,10),(8,14),(9,11),(12,13),(15,16)]
[(0,1),(2,6),(4,12),(5,7),(9,14),(10,13),(11,15)]
[(1,4),(2,3),(6,11),(7,12),(8,9),(13,14),(15,16)]
[(2,5),(3,8),(7,10),(9,12),(11,13),(14,15)]
[(1,2),(3,7),(4,5),(6,9),(8,10),(13,14)]
[(3,4),(5,7),(6,8),(9,11),(10,12)]
[(2,4),(5,6),(7,8),(9,10),(11,12)]
[(2,3),(4,5),(6,7),(8,9),(10,11),(12,13)]

 Auto generated
Sorting network for 17 inputs, 74 CEs, 10 layers:

[(1,2),(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16)]
[(1,3),(2,4),(5,7),(6,8),(9,11),(10,12),(13,15),(14,16)]
[(1,5),(2,6),(3,7),(4,8),(9,13),(10,14),(11,15),(12,16)]
[(0,3),(1,13),(2,10),(4,7),(5,11),(6,12),(8,9),(14,15)]
[(0,13),(1,8),(2,5),(3,6),(4,14),(7,15),(9,16),(10,11)]
[(0,1),(2,8),(3,4),(5,10),(6,13),(7,11),(12,14)]
[(1,5),(3,8),(4,10),(6,7),(9,12),(11,13)]
[(1,2),(4,6),(5,8),(7,10),(9,11),(12,14),(13,15)]
[(2,3),(4,5),(6,8),(7,9),(10,11),(12,13),(14,15)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16)]

This network was obtained by performing a size optimization of the network found by Ehlers&Müller (see [EM14])		 Auto generated
Sorting network for 18 inputs, 77 CEs, 12 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17)]
[(0,2),(1,3),(4,12),(5,13),(6,8),(9,11),(14,16),(15,17)]
[(0,14),(1,16),(2,15),(3,17)]
[(0,6),(1,10),(2,9),(7,16),(8,15),(11,17)]
[(1,4),(3,9),(5,7),(8,14),(10,12),(13,16)]
[(0,1),(2,5),(3,13),(4,14),(7,9),(8,10),(12,15),(16,17)]
[(1,2),(3,5),(4,6),(11,13),(12,14),(15,16)]
[(4,8),(5,12),(6,10),(7,11),(9,13)]
[(1,4),(2,8),(3,6),(5,7),(9,15),(10,12),(11,14),(13,16)]
[(2,4),(5,8),(6,10),(7,11),(9,12),(13,15)]
[(3,5),(6,8),(7,10),(9,11),(12,14)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14)]

Improved size over result (78) reported in [VM13].		 Auto generated
Sorting network for 18 inputs, 78 CEs, 11 layers:

[(0,6),(1,10),(2,15),(3,5),(4,9),(7,16),(8,13),(11,17),(12,14)]
[(0,12),(1,4),(3,11),(5,17),(6,14),(7,8),(9,10),(13,16)]
[(1,13),(2,7),(4,16),(6,9),(8,11),(10,15)]
[(0,1),(2,3),(4,12),(5,13),(7,9),(8,10),(14,15),(16,17)]
[(0,2),(1,11),(3,4),(5,7),(6,16),(10,12),(13,14),(15,17)]
[(1,8),(4,10),(5,6),(7,13),(9,16),(11,12)]
[(1,3),(2,5),(4,7),(6,8),(9,11),(10,13),(12,15),(14,16)]
[(1,2),(3,5),(4,6),(7,9),(8,10),(11,13),(12,14),(15,16)]
[(2,3),(5,8),(6,7),(9,12),(10,11),(14,15)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14)]
[(4,5),(6,7),(8,9),(10,11),(12,13)]

Matches depth of 11 layers reported in [Baddar09] while reducing size from 84 to 78.		 Auto generated
Sorting network for 19 inputs, 85 CEs, 12 layers:

[(0,12),(1,4),(2,8),(3,5),(6,17),(7,11),(9,14),(10,13),(15,16)]
[(0,2),(1,7),(3,6),(4,11),(5,17),(8,12),(10,15),(13,16),(14,18)]
[(3,10),(4,14),(5,15),(6,13),(7,9),(11,17),(16,18)]
[(0,7),(1,10),(4,6),(9,15),(11,16),(12,17),(13,14)]
[(0,3),(2,6),(5,7),(8,11),(12,16)]
[(1,8),(2,9),(3,4),(6,15),(7,13),(10,11),(12,18)]
[(1,3),(2,5),(6,9),(7,12),(8,10),(11,14),(17,18)]
[(0,1),(2,3),(4,8),(6,10),(9,12),(14,15),(16,17)]
[(1,2),(5,8),(6,7),(9,11),(10,13),(14,16),(15,17)]
[(3,6),(4,5),(7,9),(8,10),(11,12),(13,14),(15,16)]
[(3,4),(5,6),(7,8),(9,10),(11,13),(12,14)]
[(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15)]

Improved size over result (86) reported by Valsalam & Miikkulainen [VM13]		 Auto generated
Sorting network for 19 inputs, 87 CEs, 11 layers:

[(0,1),(2,3),(4,5),(6,7),(8,10),(11,12),(13,14),(15,16),(17,18)]
[(0,2),(1,3),(4,6),(5,7),(8,9),(11,13),(12,14),(15,17),(16,18)]
[(0,4),(1,5),(2,6),(3,7),(9,10),(11,15),(12,16),(13,17),(14,18)]
[(0,11),(1,8),(2,13),(3,17),(4,10),(5,6),(9,16),(12,15)]
[(1,2),(3,13),(4,12),(5,14),(6,16),(7,10),(8,15)]
[(0,1),(2,11),(3,9),(5,12),(6,15),(7,13),(10,18),(14,17)]
[(1,4),(3,8),(5,11),(6,9),(7,12),(10,13),(14,15),(16,17)]
[(2,4),(3,5),(6,7),(8,11),(9,12),(10,14),(13,15)]
[(2,3),(4,5),(6,8),(7,9),(10,11),(12,14),(13,16),(15,17)]
[(1,2),(4,6),(5,8),(7,10),(9,11),(12,13),(14,16)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16)]

 Auto generated
Sorting network for 20 inputs, 91 CEs, 12 layers:

[(0,3),(1,7),(2,5),(4,8),(6,9),(10,13),(11,15),(12,18),(14,17),(16,19)]
[(0,14),(1,11),(2,16),(3,17),(4,12),(5,19),(6,10),(7,15),(8,18),(9,13)]
[(0,4),(1,2),(3,8),(5,7),(11,16),(12,14),(15,19),(17,18)]
[(1,6),(2,12),(3,5),(4,11),(7,17),(8,15),(13,18),(14,16)]
[(0,1),(2,6),(7,10),(9,12),(13,17),(18,19)]
[(1,6),(5,9),(7,11),(8,12),(10,14),(13,18)]
[(3,5),(4,7),(8,10),(9,11),(12,15),(14,16)]
[(1,3),(2,4),(5,7),(6,10),(9,13),(12,14),(15,17),(16,18)]
[(1,2),(3,4),(6,7),(8,9),(10,11),(12,13),(15,16),(17,18)]
[(2,3),(4,6),(5,8),(7,9),(10,12),(11,14),(13,15),(16,17)]
[(4,5),(6,8),(7,10),(9,12),(11,13),(14,15)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16)]

Improved size over result (92) reported by Valsalam & Miikkulainen [VM13]		 Auto generated
Sorting network for 20 inputs, 93 CEs, 11 layers:

[(0,12),(1,13),(2,14),(3,15),(4,16),(5,17),(6,18),(7,19),(8,10),(9,11)]
[(0,2),(1,3),(4,6),(5,7),(8,9),(10,11),(12,14),(13,15),(16,18),(17,19)]
[(0,1),(2,3),(4,5),(6,7),(12,13),(14,15),(16,17),(18,19)]
[(0,4),(1,12),(2,16),(3,17),(5,8),(6,9),(7,18),(10,13),(11,14),(15,19)]
[(1,6),(3,10),(4,5),(7,11),(8,12),(9,16),(13,18),(14,15)]
[(0,4),(2,8),(3,9),(6,7),(10,16),(11,17),(12,13),(15,19)]
[(1,4),(3,6),(5,8),(7,10),(9,12),(11,14),(13,16),(15,18)]
[(2,3),(4,5),(6,8),(7,9),(10,12),(11,13),(14,15),(16,17)]
[(2,4),(3,6),(5,7),(8,10),(9,11),(12,14),(13,16),(15,17)]
[(1,2),(3,5),(6,7),(8,9),(10,11),(12,13),(14,16),(17,18)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16)]

First 3 layers inspired by [EM14]		 Auto generated
Sorting network for 21 inputs, 99 CEs, 15 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(9,11),(12,14),(13,15),(16,18),(17,19)]
[(0,8),(1,9),(2,10),(3,11),(4,12),(5,13),(6,14),(7,15)]
[(0,4),(1,5),(3,7),(6,20),(8,12),(9,13),(10,14),(15,19)]
[(2,6),(3,18),(7,20)]
[(2,16),(3,6),(5,18),(7,17),(11,20)]
[(0,2),(3,8),(6,12),(7,10),(9,16),(11,15),(13,17),(14,18),(19,20)]
[(1,7),(2,3),(4,9),(10,11),(13,16),(15,18),(17,19)]
[(1,4),(5,10),(6,13),(7,8),(11,14),(12,16),(15,17),(18,19)]
[(1,2),(3,4),(5,6),(10,12),(11,13),(14,16),(17,18)]
[(2,3),(4,5),(6,9),(10,11),(12,13),(14,15),(16,17)]
[(6,7),(8,9),(15,16)]
[(4,6),(7,8),(9,12),(13,15)]
[(3,4),(5,7),(8,10),(9,11),(12,14)]
[(5,6),(7,8),(9,10),(11,12),(13,14)]

Improved size over result (102) reported by Valsalam & Miikkulainen [VM13], breaking 100 element barrier.		 Auto generated
Sorting network for 21 inputs, 100 CEs, 12 layers:

[(0,7),(1,10),(3,5),(4,8),(6,13),(9,19),(11,14),(12,17),(15,16),(18,20)]
[(0,11),(1,15),(2,12),(3,4),(5,8),(6,9),(7,14),(10,16),(13,19),(17,20)]
[(0,6),(1,3),(2,18),(4,15),(5,10),(8,16),(11,17),(12,13),(14,20)]
[(2,6),(5,12),(7,18),(8,14),(9,11),(10,17),(13,19),(16,20)]
[(1,2),(4,7),(5,9),(6,17),(10,13),(11,12),(14,19),(15,18)]
[(0,2),(3,6),(4,5),(7,10),(8,11),(9,15),(12,16),(13,18),(14,17),(19,20)]
[(0,1),(2,3),(5,9),(6,12),(7,8),(11,14),(13,15),(16,19),(17,18)]
[(1,2),(3,9),(6,13),(10,11),(12,15),(16,17),(18,19)]
[(1,4),(2,5),(3,7),(6,10),(8,9),(11,12),(13,14),(17,18)]
[(2,4),(5,6),(7,8),(9,11),(10,13),(12,15),(14,16)]
[(3,4),(5,7),(6,8),(9,10),(11,13),(12,14),(15,16)]
[(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17)]

 Auto generated
Sorting network for 22 inputs, 106 CEs, 13 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21)]
[(0,2),(1,3),(4,6),(5,7),(8,12),(9,13),(14,16),(15,17),(18,20),(19,21)]
[(0,4),(1,5),(2,6),(3,7),(8,10),(9,12),(11,13),(14,18),(15,19),(16,20),(17,21)]
[(0,14),(1,15),(2,18),(3,19),(4,16),(5,17),(6,20),(7,21),(9,11),(10,12)]
[(2,8),(3,11),(6,9),(10,18),(12,15),(13,19)]
[(0,2),(1,10),(3,16),(5,18),(6,14),(7,15),(8,12),(9,13),(11,20),(19,21)]
[(2,6),(3,10),(4,8),(5,12),(9,16),(11,18),(13,17),(15,19)]
[(1,4),(7,13),(8,14),(9,12),(17,20)]
[(1,2),(3,8),(4,6),(7,11),(10,14),(13,18),(15,17),(19,20)]
[(2,4),(5,10),(7,9),(11,16),(12,14),(17,19)]
[(5,6),(7,8),(9,11),(10,12),(13,14),(15,16)]
[(3,5),(6,7),(8,10),(9,12),(11,13),(14,15),(16,18)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18)]

Improved size over result (108) from Valsalam & Miikkulainen [VM13].		 Auto generated
Sorting network for 22 inputs, 107 CEs, 12 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(11,13),(14,16),(15,17),(18,20),(19,21)]
[(0,4),(1,5),(2,6),(3,7),(8,12),(9,13),(14,18),(15,19),(16,20),(17,21)]
[(0,14),(1,15),(2,18),(3,19),(4,16),(5,17),(6,20),(7,21),(9,11),(10,12)]
[(0,8),(2,10),(4,14),(5,12),(6,15),(7,17),(9,16),(11,19),(13,21)]
[(1,9),(2,4),(3,16),(5,18),(6,10),(7,13),(8,14),(11,15),(12,20),(17,19)]
[(1,8),(3,11),(4,5),(7,12),(9,14),(10,18),(13,20),(16,17)]
[(1,2),(3,5),(4,8),(6,9),(7,11),(10,14),(12,15),(13,17),(16,18),(19,20)]
[(2,4),(3,6),(5,9),(7,10),(11,14),(12,16),(15,18),(17,19)]
[(3,4),(5,7),(6,8),(9,11),(10,12),(13,15),(14,16),(17,18)]
[(5,6),(7,8),(9,10),(11,12),(13,14),(15,16)]
[(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17)]

 Auto generated
Sorting network for 23 inputs, 114 CEs, 14 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(9,11),(12,14),(13,15),(16,18),(17,19),(21,22)]
[(0,4),(1,5),(2,6),(3,7),(8,12),(9,13),(10,14),(11,15),(17,21),(18,20),(19,22)]
[(0,8),(1,9),(2,10),(3,11),(4,12),(5,13),(6,14),(7,15)]
[(1,2),(5,18),(7,19),(9,16),(10,21),(12,20),(15,22)]
[(5,9),(6,7),(10,18),(11,21),(12,17),(13,20),(14,15)]
[(3,17),(6,16),(7,14),(8,12),(15,19),(20,21)]
[(3,4),(5,8),(6,10),(9,12),(13,16),(14,15),(17,18),(19,21)]
[(0,5),(1,8),(2,12),(3,9),(4,10),(7,13),(11,17),(14,16),(18,20)]
[(2,6),(3,5),(4,8),(7,11),(10,12),(13,18),(14,17),(15,20)]
[(1,3),(2,5),(6,9),(7,10),(11,13),(12,14),(15,18),(16,17),(19,20)]
[(2,3),(4,6),(8,9),(11,12),(13,14),(15,16),(17,19)]
[(3,4),(5,6),(7,8),(9,10),(12,13),(14,15),(17,18)]
[(4,5),(6,7),(8,9),(10,11),(16,17)]

Reduction in size vs. 118 reported in [Baddar09]		 Auto generated
Sorting network for 23 inputs, 115 CEs, 13 layers:

[(0,20),(1,12),(2,16),(4,6),(5,10),(7,21),(8,14),(9,15),(11,22),(13,18),(17,19)]
[(0,3),(1,11),(2,7),(4,17),(5,13),(6,19),(8,9),(10,18),(12,22),(14,15),(16,21)]
[(0,1),(2,4),(3,12),(5,8),(6,9),(7,10),(11,20),(13,16),(14,17),(15,18),(19,21)]
[(2,5),(4,8),(6,11),(7,14),(9,16),(12,17),(15,19),(18,21)]
[(1,8),(3,14),(4,7),(9,20),(10,12),(11,13),(15,22),(16,19)]
[(0,7),(1,5),(3,4),(6,11),(8,15),(9,14),(10,13),(12,17),(18,22),(19,20)]
[(0,2),(1,6),(4,7),(5,9),(8,10),(13,15),(14,18),(16,19),(17,22),(20,21)]
[(2,3),(4,5),(6,8),(7,9),(10,11),(12,13),(14,16),(15,17),(18,19),(21,22)]
[(1,2),(3,6),(4,10),(7,8),(9,11),(12,14),(13,19),(15,16),(17,20)]
[(2,3),(5,10),(6,7),(8,9),(13,18),(14,15),(16,17),(20,21)]
[(3,4),(5,7),(10,12),(11,13),(16,18),(19,20)]
[(4,6),(8,10),(9,12),(11,14),(13,15),(17,19)]
[(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18)]

Obtained by removing highest input from 24 inputs case with 13 layers.		 Auto generated
Sorting network for 23 inputs, 116 CEs, 12 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(9,11),(12,14),(13,15),(17,19),(18,20),(21,22)]
[(0,4),(1,5),(2,6),(3,7),(8,12),(9,13),(10,14),(11,15),(16,21),(17,22)]
[(1,10),(2,9),(3,11),(6,19),(12,17),(14,22),(16,18),(20,21)]
[(0,16),(1,2),(3,21),(4,17),(5,14),(6,13),(7,22),(9,18),(10,20),(15,19)]
[(1,10),(2,9),(3,17),(4,12),(5,18),(6,20),(7,15),(8,16),(11,14),(13,21),(19,22)]
[(0,8),(1,4),(2,10),(3,9),(5,6),(11,21),(12,16),(13,20),(14,15),(17,18)]
[(2,8),(3,5),(4,12),(6,9),(7,11),(10,16),(13,17),(15,21),(18,20)]
[(1,2),(4,8),(5,10),(6,12),(7,13),(9,16),(11,18),(14,17),(15,19)]
[(2,4),(3,5),(6,8),(7,9),(10,12),(11,13),(14,16),(15,20),(17,18),(19,21)]
[(3,6),(5,8),(7,10),(9,12),(11,14),(13,16),(15,17),(18,20)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(19,20)]

 Auto generated
Sorting network for 24 inputs, 120 CEs, 13 layers:

[(0,20),(1,12),(2,16),(3,23),(4,6),(5,10),(7,21),(8,14),(9,15),(11,22),(13,18),(17,19)]
[(0,3),(1,11),(2,7),(4,17),(5,13),(6,19),(8,9),(10,18),(12,22),(14,15),(16,21),(20,23)]
[(0,1),(2,4),(3,12),(5,8),(6,9),(7,10),(11,20),(13,16),(14,17),(15,18),(19,21),(22,23)]
[(2,5),(4,8),(6,11),(7,14),(9,16),(12,17),(15,19),(18,21)]
[(1,8),(3,14),(4,7),(9,20),(10,12),(11,13),(15,22),(16,19)]
[(0,7),(1,5),(3,4),(6,11),(8,15),(9,14),(10,13),(12,17),(16,23),(18,22),(19,20)]
[(0,2),(1,6),(4,7),(5,9),(8,10),(13,15),(14,18),(16,19),(17,22),(21,23)]
[(2,3),(4,5),(6,8),(7,9),(10,11),(12,13),(14,16),(15,17),(18,19),(20,21)]
[(1,2),(3,6),(4,10),(7,8),(9,11),(12,14),(13,19),(15,16),(17,20),(21,22)]
[(2,3),(5,10),(6,7),(8,9),(13,18),(14,15),(16,17),(20,21)]
[(3,4),(5,7),(10,12),(11,13),(16,18),(19,20)]
[(4,6),(8,10),(9,12),(11,14),(13,15),(17,19)]
[(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18)]

Reduction in size vs. 123 reported in [Baddar09]		 Auto generated
Sorting network for 24 inputs, 122 CEs, 12 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21),(22,23)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(9,11),(12,14),(13,15),(16,18),(17,19),(20,22),(21,23)]
[(0,4),(1,5),(2,6),(3,7),(8,12),(9,13),(10,14),(11,15),(16,20),(17,21),(18,22),(19,23)]
[(0,16),(1,18),(2,17),(3,19),(4,20),(5,22),(6,21),(7,23),(9,10),(13,14)]
[(2,10),(3,11),(5,18),(6,14),(7,15),(8,16),(9,17),(12,20),(13,21)]
[(0,8),(1,9),(2,12),(3,20),(4,16),(5,13),(6,17),(7,19),(10,18),(11,21),(14,22),(15,23)]
[(1,8),(3,16),(4,12),(5,10),(6,9),(7,20),(11,19),(13,18),(14,17),(15,22)]
[(2,4),(3,5),(7,13),(9,12),(10,16),(11,14),(18,20),(19,21)]
[(1,2),(4,8),(5,9),(6,10),(7,11),(12,16),(13,17),(14,18),(15,19),(21,22)]
[(2,4),(3,8),(5,6),(7,9),(10,12),(11,13),(14,16),(15,20),(17,18),(19,21)]
[(3,5),(6,8),(7,10),(9,12),(11,14),(13,16),(15,17),(18,20)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(19,20)]

 Auto generated
Sorting network for 25 inputs, 130 CEs, 15 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21),(22,23)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(9,11),(12,14),(13,15),(16,18),(17,19),(21,22),(23,24)]
[(0,4),(1,5),(2,6),(3,7),(8,12),(9,13),(10,14),(11,15),(18,21),(20,23),(22,24)]
[(0,8),(1,9),(2,10),(3,11),(4,12),(5,13),(6,14),(7,15),(16,20),(17,22),(19,24),(21,23)]
[(1,18),(3,21),(5,23),(6,19),(11,14),(15,24)]
[(1,16),(3,17),(6,9),(7,11),(13,19),(14,23)]
[(0,1),(2,16),(3,8),(7,20),(10,13),(11,22),(15,23)]
[(1,2),(5,10),(7,18),(11,21),(15,20),(19,22)]
[(4,7),(5,6),(9,18),(10,17),(11,12),(13,21),(14,15),(19,20),(22,23)]
[(3,4),(7,8),(9,10),(11,16),(12,17),(13,18),(19,21),(20,22)]
[(1,3),(2,4),(5,11),(6,16),(7,9),(8,10),(12,13),(14,19),(15,18)]
[(2,3),(5,7),(6,9),(8,11),(10,16),(12,14),(15,17)]
[(3,5),(4,6),(7,8),(9,11),(10,12),(13,14),(15,16),(17,18)]
[(4,7),(6,8),(9,10),(11,12),(13,15),(14,16),(17,19),(18,21)]
[(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21)]

Improved size vs. Batcher odd-even merge.		 Auto generated
Sorting network for 25 inputs, 131 CEs, 13 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21),(22,23)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(9,11),(12,14),(13,15),(16,18),(17,19),(20,22),(21,24)]
[(0,4),(1,5),(2,6),(3,7),(8,12),(9,13),(10,14),(11,15),(16,20),(21,22),(23,24)]
[(0,8),(1,12),(2,10),(3,14),(4,9),(5,13),(6,11),(7,15),(17,22),(18,21),(19,24)]
[(1,18),(3,9),(5,17),(6,20),(7,13),(11,14),(12,22),(15,24),(21,23)]
[(1,16),(3,12),(5,21),(6,18),(7,11),(10,17),(14,23),(19,20)]
[(0,1),(2,5),(4,16),(6,8),(7,18),(9,21),(10,14),(11,13),(12,19),(15,23),(20,22)]
[(1,2),(3,5),(4,6),(7,9),(8,12),(10,16),(11,20),(13,22),(14,17),(15,18),(19,21)]
[(1,4),(2,6),(3,7),(5,9),(8,10),(11,14),(12,16),(13,17),(15,19),(18,20),(22,23)]
[(2,4),(3,8),(5,10),(7,12),(9,16),(11,15),(13,19),(14,21),(17,18),(20,22)]
[(3,4),(5,8),(6,7),(9,12),(10,11),(13,16),(14,15),(17,19),(18,21)]
[(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(20,21)]
[(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19)]

Improved size and depth over obtainable metrics by Batcher odd-even merge. The existence of a 13 layer network was conjectured in the conclusion of [Ehlers17].		 Auto generated
Sorting network for 26 inputs, 139 CEs, 14 layers:

[(0,1),(2,3),(4,21),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(19,20),(22,23),(24,25)]
[(0,24),(1,25),(3,21),(4,22),(5,7),(6,8),(9,11),(10,12),(13,15),(14,16),(17,19),(18,20)]
[(0,4),(2,22),(3,23),(5,9),(6,10),(7,11),(8,12),(13,17),(14,18),(15,19),(16,20),(21,25)]
[(0,2),(1,3),(4,21),(5,13),(6,14),(7,15),(8,16),(9,17),(10,18),(11,19),(12,20),(22,24),(23,25)]
[(0,5),(1,7),(2,4),(3,10),(15,22),(18,24),(20,25),(21,23)]
[(2,9),(3,7),(4,14),(5,13),(6,15),(10,19),(11,21),(12,20),(16,23),(18,22)]
[(1,5),(2,6),(3,15),(7,17),(8,18),(10,22),(11,13),(12,14),(19,23),(20,24)]
[(1,2),(4,7),(5,11),(8,9),(10,12),(13,15),(14,20),(16,17),(18,21),(23,24)]
[(3,8),(4,6),(7,16),(9,18),(10,13),(12,15),(17,22),(19,21)]
[(4,5),(6,11),(7,9),(14,19),(16,18),(20,21)]
[(2,4),(3,6),(7,10),(8,11),(9,12),(13,16),(14,17),(15,18),(19,22),(21,23)]
[(3,4),(5,8),(6,7),(9,10),(11,13),(12,14),(15,16),(17,20),(18,19),(21,22)]
[(5,6),(7,8),(9,11),(10,13),(12,15),(14,16),(17,18),(19,20)]
[(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21)]

Improved size over Batcher odd-even merge		 Auto generated
Sorting network for 26 inputs, 141 CEs, 13 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21),(22,23),(24,25)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(9,11),(14,16),(15,17),(18,20),(19,21),(22,24),(23,25)]
[(0,4),(1,5),(2,6),(3,7),(8,14),(9,16),(10,13),(11,17),(12,15),(18,22),(19,23),(20,24),(21,25)]
[(0,18),(1,19),(2,20),(3,21),(4,22),(5,23),(6,24),(7,25),(8,12),(10,14),(11,15),(13,17)]
[(1,18),(2,10),(3,20),(4,8),(5,22),(6,14),(7,24),(9,12),(11,19),(13,16),(15,23),(17,21)]
[(0,4),(1,9),(3,13),(5,15),(6,18),(7,19),(8,11),(10,20),(12,22),(14,17),(16,24),(21,25)]
[(2,4),(3,11),(5,9),(10,12),(13,15),(14,22),(16,20),(21,23)]
[(1,4),(3,8),(6,10),(7,13),(9,11),(12,18),(14,16),(15,19),(17,22),(21,24)]
[(1,2),(3,6),(4,5),(7,12),(8,10),(9,14),(11,16),(13,18),(15,17),(19,22),(20,21),(23,24)]
[(2,3),(4,6),(5,10),(7,9),(11,13),(12,14),(15,20),(16,18),(19,21),(22,23)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(19,20),(21,22)]
[(5,7),(6,8),(9,11),(10,12),(13,15),(14,16),(17,19),(18,20)]
[(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21)]

Improved depth from 14 that could be achieved by Batcher odd-even merge		 Auto generated
Sorting network for 27 inputs, 147 CEs, 16 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,14),(15,16),(17,18),(19,20),(21,22),(23,24),(25,26)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(9,11),(12,13),(15,17),(16,18),(19,21),(20,22),(23,25),(24,26)]
[(0,23),(1,24),(2,25),(3,26),(4,8),(5,9),(6,10),(7,11),(13,14),(15,19),(16,20),(17,21),(18,22)]
[(0,4),(1,6),(2,19),(3,20),(5,13),(9,21),(11,14),(12,16),(17,23),(18,24),(22,26)]
[(5,17),(6,16),(7,22),(9,25),(10,24),(12,15),(13,20),(14,26)]
[(1,12),(4,15),(7,23),(10,19),(11,16),(13,18),(20,24),(22,25)]
[(0,1),(6,12),(8,11),(9,15),(10,17),(14,24),(16,21),(18,19)]
[(1,4),(2,8),(3,11),(12,15),(14,20),(16,22),(21,25)]
[(2,5),(3,17),(8,13),(11,23),(21,22),(24,25)]
[(1,2),(3,10),(5,6),(7,13),(11,15),(14,21),(18,23),(20,22)]
[(4,5),(6,9),(7,8),(13,17),(14,16),(19,23),(22,24)]
[(2,4),(3,6),(5,7),(8,12),(9,10),(11,13),(14,18),(15,17),(16,19),(21,23)]
[(3,5),(6,8),(7,9),(10,12),(11,14),(13,16),(15,18),(17,19),(20,21),(22,23)]
[(5,6),(8,11),(9,10),(12,14),(13,15),(17,18),(19,21)]
[(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,20),(21,22)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(19,20)]

Improved size compared to 150 that could be obtained by Batcher odd-even merge		 Auto generated
Sorting network for 27 inputs, 148 CEs, 14 layers:

[(0,17),(1,20),(2,23),(3,24),(4,9),(5,18),(6,16),(7,13),(8,15),(10,14),(11,21),(19,26),(22,25)]
[(0,4),(1,8),(2,19),(3,7),(5,6),(9,17),(10,11),(12,25),(13,24),(14,21),(15,20),(16,18),(23,26)]
[(0,2),(1,3),(4,23),(5,10),(6,14),(7,8),(9,19),(11,16),(12,22),(13,15),(17,26),(18,21),(20,24)]
[(1,5),(2,12),(3,6),(4,9),(7,11),(8,18),(10,13),(14,15),(16,20),(19,23),(21,24),(25,26)]
[(0,2),(3,7),(4,22),(5,10),(8,13),(9,25),(11,14),(15,18),(20,21)]
[(0,1),(2,3),(4,5),(6,14),(7,10),(9,12),(11,17),(19,22),(23,25)]
[(1,2),(3,6),(5,11),(7,9),(8,19),(12,18),(14,26),(16,23),(17,22),(20,25)]
[(3,5),(6,16),(9,14),(10,12),(13,17),(15,23),(18,25),(19,20),(21,22),(24,26)]
[(2,10),(5,9),(6,8),(11,13),(12,14),(15,16),(17,21),(22,24)]
[(2,7),(3,6),(8,10),(9,11),(12,15),(13,19),(14,16),(17,20),(18,21),(22,23),(24,25)]
[(4,7),(5,8),(6,9),(10,11),(12,13),(14,17),(15,19),(16,20),(18,22),(23,24)]
[(1,4),(3,7),(5,6),(8,10),(9,12),(11,13),(14,15),(16,17),(18,19),(20,21)]
[(2,4),(6,7),(8,9),(10,12),(11,14),(13,15),(16,18),(17,19),(20,22),(21,23)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(19,20),(21,22)]

 Auto generated
Sorting network for 28 inputs, 155 CEs, 14 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21),(22,23),(24,25),(26,27)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(9,11),(12,14),(13,15),(16,18),(17,19),(20,22),(21,23),(24,26),(25,27)]
[(0,4),(1,5),(2,6),(3,7),(8,12),(9,13),(14,18),(15,19),(20,24),(21,25),(22,26),(23,27)]
[(0,20),(1,21),(2,22),(3,23),(4,24),(5,25),(6,26),(7,27),(9,17),(10,18),(11,15),(12,16)]
[(1,2),(4,20),(5,6),(7,23),(8,12),(9,16),(10,14),(11,18),(13,17),(15,19),(21,22),(25,26)]
[(0,8),(1,9),(2,12),(3,5),(4,10),(6,16),(7,13),(11,21),(14,20),(15,25),(17,23),(18,26),(19,27),(22,24)]
[(2,4),(3,7),(5,17),(8,14),(9,11),(10,22),(13,19),(16,18),(20,24),(23,25)]
[(1,8),(3,9),(5,11),(6,10),(7,15),(12,20),(16,22),(17,21),(18,24),(19,26)]
[(1,2),(4,6),(5,9),(10,16),(11,17),(12,14),(13,15),(18,22),(21,23),(25,26)]
[(4,8),(6,12),(7,11),(10,14),(13,17),(15,21),(16,20),(19,23)]
[(2,4),(6,8),(7,16),(9,14),(10,12),(11,20),(13,18),(15,17),(19,21),(23,25)]
[(3,10),(5,12),(7,9),(11,13),(14,16),(15,22),(17,24),(18,20)]
[(3,6),(5,8),(7,10),(9,12),(11,14),(13,16),(15,18),(17,20),(19,22),(21,24)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(19,20),(21,22),(23,24)]

Improved size over 156 that could be obtained by Batcher odd-even merge		 Auto generated
Sorting network for 29 inputs, 164 CEs, 15 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,28),(17,26),(18,25),(19,23),(21,27),(22,24)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(9,11),(12,14),(13,15),(17,22),(18,19),(20,27),(23,25),(24,26)]
[(0,4),(1,5),(2,6),(3,7),(8,12),(9,13),(10,14),(11,15),(16,20),(17,18),(19,22),(23,24),(25,26),(27,28)]
[(0,8),(1,9),(2,10),(3,11),(4,12),(5,13),(6,14),(7,15),(16,18),(20,22),(21,25),(24,27),(26,28)]
[(1,8),(2,24),(4,19),(5,20),(6,21),(7,27),(9,18),(10,23),(11,26),(13,22),(14,25),(15,28),(16,17)]
[(0,6),(2,4),(3,24),(5,10),(12,19),(13,18),(14,21),(15,25),(20,23),(26,27)]
[(0,16),(1,6),(3,12),(4,8),(5,17),(7,24),(14,20),(15,26),(18,21),(19,23),(25,27)]
[(1,5),(2,16),(3,10),(6,9),(7,18),(8,17),(11,19),(13,14),(15,22),(21,23),(25,26)]
[(1,2),(3,5),(4,8),(6,16),(7,11),(9,17),(10,12),(14,20),(15,18),(19,24),(22,27)]
[(4,6),(9,16),(10,13),(11,19),(12,14),(20,21),(22,26),(23,24)]
[(2,4),(3,6),(7,16),(8,9),(11,17),(15,19),(18,23),(24,25)]
[(3,4),(5,9),(7,10),(11,13),(12,16),(14,17),(15,20),(19,21),(22,24)]
[(5,8),(6,7),(9,12),(10,11),(13,14),(15,16),(17,20),(18,19),(21,23),(24,25)]
[(5,6),(7,8),(9,10),(11,12),(13,15),(14,16),(17,18),(19,20),(21,22)]
[(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21),(22,23)]

Improved size over 165 that could be obtained by Batcher odd-even merge		 Auto generated
Sorting network for 29 inputs, 166 CEs, 14 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21),(22,23),(24,25),(26,27)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(9,11),(12,14),(13,15),(16,18),(17,19),(20,22),(21,23),(24,26),(25,27)]
[(0,4),(1,5),(2,6),(3,7),(8,12),(9,13),(10,14),(11,15),(16,20),(17,21),(18,22),(19,23),(24,28)]
[(0,8),(1,9),(2,10),(3,11),(4,12),(5,13),(6,14),(7,15),(16,24),(17,25),(18,26),(19,27),(20,28)]
[(0,16),(1,8),(2,4),(3,12),(5,10),(6,9),(7,14),(11,13),(17,24),(18,20),(19,28),(21,26),(22,25),(23,27)]
[(1,2),(3,5),(4,8),(6,22),(7,11),(9,25),(10,12),(13,14),(17,18),(19,21),(20,24),(26,28)]
[(1,17),(2,18),(3,19),(4,20),(5,10),(7,23),(8,24),(11,27),(12,28),(13,25),(21,26)]
[(3,17),(4,16),(5,21),(6,18),(7,9),(8,20),(10,26),(11,23),(14,28),(15,27),(22,24)]
[(1,4),(3,8),(5,16),(7,17),(9,21),(10,22),(11,19),(12,20),(14,24),(15,26),(23,28)]
[(2,5),(7,8),(9,18),(11,17),(12,16),(13,22),(14,20),(15,19),(23,24)]
[(2,4),(6,12),(9,16),(10,11),(13,17),(14,18),(15,22),(19,25),(20,21)]
[(5,6),(8,12),(9,10),(11,13),(14,16),(15,17),(18,20),(19,23),(21,22),(25,26)]
[(3,5),(6,7),(8,9),(10,12),(11,14),(13,16),(15,18),(17,20),(19,21),(22,23),(24,25),(26,28)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(19,20),(21,22),(23,24),(25,26),(27,28)]

Obtained by removing 3 inputs from the 32 input network with 185 elements and 14 layers.		 Auto generated
Sorting network for 30 inputs, 172 CEs, 14 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21),(22,23),(24,25),(26,27),(28,29)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(9,11),(13,15),(14,16),(18,20),(19,21),(22,24),(23,25),(26,28),(27,29)]
[(0,4),(1,5),(2,6),(3,7),(8,14),(9,17),(10,16),(12,20),(13,19),(15,21),(22,26),(23,27),(24,28),(25,29)]
[(0,8),(1,9),(2,14),(3,17),(4,10),(5,11),(6,16),(12,26),(13,23),(15,27),(18,24),(19,25),(20,28),(21,29)]
[(1,13),(2,12),(3,15),(4,18),(5,19),(6,20),(7,21),(8,22),(9,23),(10,24),(11,25),(14,26),(16,28),(17,27)]
[(0,4),(2,8),(3,13),(5,9),(6,22),(7,23),(10,12),(11,15),(14,18),(16,26),(17,19),(20,24),(21,27),(25,29)]
[(0,2),(1,14),(3,5),(4,8),(9,13),(11,17),(12,18),(15,28),(16,20),(21,25),(24,26),(27,29)]
[(2,4),(5,9),(6,14),(7,13),(8,10),(15,23),(16,22),(19,21),(20,24),(25,27)]
[(6,8),(7,11),(10,14),(12,16),(13,17),(15,19),(18,22),(21,23)]
[(4,6),(7,9),(8,10),(11,13),(12,14),(15,17),(16,18),(19,21),(20,22),(23,25)]
[(1,8),(3,18),(5,20),(7,22),(9,24),(10,12),(11,26),(13,15),(14,16),(17,19),(21,28)]
[(1,2),(3,10),(5,12),(7,14),(9,16),(11,18),(13,20),(15,22),(17,24),(19,26),(27,28)]
[(2,4),(3,6),(5,8),(7,10),(9,12),(11,14),(13,16),(15,18),(17,20),(19,22),(21,24),(23,26),(25,27)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(19,20),(21,22),(23,24),(25,26)]

Combines best known size and depth. An interesting pattern emerged through evolution in the last 4 layers: each layer "specializes" in elements bridging vertical distances of respectively 15, 7, 3 and 1, equally spaced with a stride of 2. This pattern is also typical for "pairwise" sorting networks [Par92].		 Auto generated
Sorting network for 31 inputs, 180 CEs, 14 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21),(22,23),(24,25),(26,27),(28,29)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(9,11),(12,14),(13,15),(16,18),(17,19),(20,22),(21,23),(24,26),(25,27),(28,30)]
[(0,4),(1,5),(2,6),(3,7),(8,12),(9,13),(10,14),(11,15),(16,20),(17,21),(18,22),(19,23),(24,28),(25,29),(26,30)]
[(0,8),(1,9),(2,10),(3,11),(4,12),(5,13),(6,14),(7,15),(16,24),(17,25),(18,26),(19,27),(20,28),(21,29),(22,30)]
[(0,16),(1,8),(2,4),(3,12),(5,10),(6,9),(7,14),(11,13),(17,24),(18,20),(19,28),(21,26),(22,25),(23,30),(27,29)]
[(1,2),(3,5),(4,8),(6,22),(7,11),(9,25),(10,12),(13,14),(17,18),(19,21),(20,24),(23,27),(26,28),(29,30)]
[(1,17),(2,18),(3,19),(4,20),(5,10),(7,23),(8,24),(11,27),(12,28),(13,29),(14,30),(21,26)]
[(3,17),(4,16),(5,21),(6,18),(7,9),(8,20),(10,26),(11,23),(13,25),(14,28),(15,27),(22,24)]
[(1,4),(3,8),(5,16),(7,17),(9,21),(10,22),(11,19),(12,20),(14,24),(15,26),(23,28),(27,30)]
[(2,5),(7,8),(9,18),(11,17),(12,16),(13,22),(14,20),(15,19),(23,24),(26,29)]
[(2,4),(6,12),(9,16),(10,11),(13,17),(14,18),(15,22),(19,25),(20,21),(27,29)]
[(5,6),(8,12),(9,10),(11,13),(14,16),(15,17),(18,20),(19,23),(21,22),(25,26)]
[(3,5),(6,7),(8,9),(10,12),(11,14),(13,16),(15,18),(17,20),(19,21),(22,23),(24,25),(26,28)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(19,20),(21,22),(23,24),(25,26),(27,28)]

Obtained by removing one input from the network with 32 inputs, 185 elements and 14 layers.		 Auto generated
Sorting network for 32 inputs, 185 CEs, 14 layers:

[(0,1),(2,3),(4,5),(6,7),(8,9),(10,11),(12,13),(14,15),(16,17),(18,19),(20,21),(22,23),(24,25),(26,27),(28,29),(30,31)]
[(0,2),(1,3),(4,6),(5,7),(8,10),(9,11),(12,14),(13,15),(16,18),(17,19),(20,22),(21,23),(24,26),(25,27),(28,30),(29,31)]
[(0,4),(1,5),(2,6),(3,7),(8,12),(9,13),(10,14),(11,15),(16,20),(17,21),(18,22),(19,23),(24,28),(25,29),(26,30),(27,31)]
[(0,8),(1,9),(2,10),(3,11),(4,12),(5,13),(6,14),(7,15),(16,24),(17,25),(18,26),(19,27),(20,28),(21,29),(22,30),(23,31)]
[(0,16),(1,8),(2,4),(3,12),(5,10),(6,9),(7,14),(11,13),(15,31),(17,24),(18,20),(19,28),(21,26),(22,25),(23,30),(27,29)]
[(1,2),(3,5),(4,8),(6,22),(7,11),(9,25),(10,12),(13,14),(17,18),(19,21),(20,24),(23,27),(26,28),(29,30)]
[(1,17),(2,18),(3,19),(4,20),(5,10),(7,23),(8,24),(11,27),(12,28),(13,29),(14,30),(21,26)]
[(3,17),(4,16),(5,21),(6,18),(7,9),(8,20),(10,26),(11,23),(13,25),(14,28),(15,27),(22,24)]
[(1,4),(3,8),(5,16),(7,17),(9,21),(10,22),(11,19),(12,20),(14,24),(15,26),(23,28),(27,30)]
[(2,5),(7,8),(9,18),(11,17),(12,16),(13,22),(14,20),(15,19),(23,24),(26,29)]
[(2,4),(6,12),(9,16),(10,11),(13,17),(14,18),(15,22),(19,25),(20,21),(27,29)]
[(5,6),(8,12),(9,10),(11,13),(14,16),(15,17),(18,20),(19,23),(21,22),(25,26)]
[(3,5),(6,7),(8,9),(10,12),(11,14),(13,16),(15,18),(17,20),(19,21),(22,23),(24,25),(26,28)]
[(3,4),(5,6),(7,8),(9,10),(11,12),(13,14),(15,16),(17,18),(19,20),(21,22),(23,24),(25,26),(27,28)]

This network was obtained by evolution using a fixed prefix in its first 4 layers. Its size and depth combine the best results that can be achieved using a Batcher odd-even merge of either twice the 16 input network with 60 CEs and 10 layers or twice the 16 input network with 61 CEs and 9 layers.		 Auto generated

References

[Baddar09]Sherenaz W. Al-Haj Baddar. Finding Better Sorting Networks. Dissertation submitted to Kent State University in partial fulfillment of the requirements for the degree of Doctor of Philosophy, 2009.
[BZ14]D. Bundala, J. Závodný. Optimal sorting networks. In LATA 2014, volume 8370 of LNCS, Springer, 2014.
[CCEMS16]M. Codish, L. Cruz-Filipe, T. Ehlers, M. Müller, P. Schneider-Kamp. Sorting networks: To the end and back again, Journal of Computer and System Sciences, 28 April 2016.
[CCFS16]M. Codish, L. Cruz-Filipe, M. Frank, P. Schneider-Kamp. Sorting nine inputs requires twenty-five comparisons. Journal of Computer and System Sciences, Vol. 82 iss. 3, May 2016.
[Ehlers17]T. Ehlers. Merging almost sorted sequences yields a 24-sorter. Information Processing Letters Vol. 118 Issue C, February 2017.
[EM14]T. Ehlers and M. Müller. Faster Sorting Networks for 17, 19 and 20 Inputs, 2014.
[Fon18]José A. R. Fonollosa. Joint Size and Depth Optimization of Sorting Networks, 2018.
[Harder19]Harder, Jannis. "sortnetopt". GitHub. Retrieved 7 December 2019.
[Par89]Parberry, Ian. A computer assisted optimal depth lower bound for sorting networks with nine inputs, 1989.
[Par92]Parberry, Ian. The Pairwise Sorting Network, 1992.
[TAOCPv3]D. E. Knuth. The art of computer programming, vol. 3: Sorting and Searching, 2nd edition. Addison-Wesley, 1998.
[VM13]V. K. Valsalam and R. Miikkulainen. Using symmetry and evolutionary search to minimize sorting networks. Journal of Machine Learning Research, 14:303–331, 2013.

History

2024-02-25Minor improvement for 25 inputs.
2023-12-16Minor improvement for 30 inputs.
2023-11-09Minor improvements for 26 and 27 inputs.
2022-11-27Improved size for 27 inputs.
2022-09-18Minor improvement for 28 inputs.
2022-07-04Improved size for 25 inputs, minor improvement for 24 inputs.
2022-06-20Using symmetric network for 14 inputs, 9 layers. Minor improvements for 25 and 26 inputs.
2022-05-28Minor improvements for 21, 22, 23, 25 and 26 inputs.
2022-05-17Minor improvements for 18 inputs. Replaced networks for 22 inputs by symmetric variants with identical metrics.
2022-02-15Small improvement for 29 inputs. Add reference to extended list.
2022-01-23Improved size for 29 inputs.
2022-01-21Small improvement for 27 inputs.
2022-01-15Improved size for 22 inputs. Browser compatibility fix.
2022-01-09Small improvements for 23 and 27 inputs, add OEIS links.
2022-01-02Improved size for 21, 23, 25 and 27 inputs using similarly structured prefix. Small improvements for 22 and 28 inputs.
2021-12-28Small improvement for 19 inputs. Use JavaScript based generation of diagrams. Add reference for size 9 and 10 depth optimality.
2020-07-04Improved size for 18 inputs. Small improvement for 22 inputs.
2020-06-30Combining best depth and size in a single network for 21 inputs.
2020-06-27Small improvement for networks of 29...32 inputs and 14 layers.
2020-06-16Improved depth upper bound for 25 and 26 inputs.
2020-06-07Editorials and small improvement for 22 inputs.
2020-05-30Update lower size bounds.
2018-07-18Improved sizes for 23, 24, 25 and 26 inputs. Small improvement for 21 inputs.
2018-06-12Improved size for 21 inputs. Small improvements for 22 inputs. Add findings from [Fon18]
2018-01-02Add improved size for 22 inputs. Add 'bounds' columns to summary table. Small improvements to 17, 21 and 22 input combinations.
2017-12-27Initial draft list

Page updated on Sun Feb 25 19:00:17 2024

See SorterHunter repo for previous versions.