The sorting networks on this page have been optimized to reduce the worst case number of swaps executed for any input permutation.
For some applications (e.g. real-time computing), understanding of this worst case behaviour is important.
The network will still perform all comparisons, we just try to limit the number of elements that actually change the order.
The size and depth of the networks matches the smallest size networks from the regular list of sorting networks.
Whether the reduction of swaps actually reduces the resource consumption will depend on the target architecture.
You may notice this list is shorter than the others on this site. This is because of the amount of computation involved to verify the worst case swap count.
The networks were obtained by applying input order transformations on the outputs from SorterHunter, trying to improve the swap count.
For questions, remarks, or to contribute improved results please contact bert.o.dobbelaere[at]telenet[dot]be.
For optimization of the average number of swaps, see this page.
| Number of inputs | Size | Depth | Max swap count | Average swap count | Comments |
|---|---|---|---|---|---|
| 2 | 1 | 1 | 1 worst case | 0.5 | |
| 3 | 3 | 3 | 2 worst case | 1.16666667 | |
| 4 | 5 | 3 | 4 worst case | 2.33333333 | |
| 5 | 9 | 5 | 6 worst case | 3.13333333 | |
| 6 | 12 | 5 | 8 worst case | 4.7 | |
| 7 | 16 | 6 | 11 worst case | 5.89047619 | |
| 8 | 19 | 6 | 14 worst case | 7.94285714 | |
| 9 | 25 | 7 | 17 worst case | 9.02539683 | |
| 10 | 29 | 8 | 21 worst case | 10.77619048 | |
| 11 | 35 | 8 | 23 worst case | 13.10577201 | |
| 12 | 39 | 9 | 27 worst case | 14.60606061 | |
| 13 | 45 | 10 | 32 worst case | 16.91999112 | |
| 14 | 51 | 10 | 35 worst case | 19.88281718 | |
| 15 | 56 | 10 | 41 worst case | 21.45675436 | |
| 16 | 60 | 10 | 46 worst case | 23.86853147 |
| Sorting network for 2 inputs, 1 CE, 1 layer. Worst case 1 swaps, 0.5 swaps on average. [(0,1)] | Auto generated |
| Sorting network for 3 inputs, 3 CEs, 3 layers. Worst case 2 swaps, 1.16666667 swaps on average. [(0,2)] | Auto generated |
| Sorting network for 4 inputs, 5 CEs, 3 layers. Worst case 4 swaps, 2.33333333 swaps on average. [(0,3),(1,2)] | Auto generated |
| Sorting network for 5 inputs, 9 CEs, 5 layers. Worst case 6 swaps, 3.13333333 swaps on average. [(0,4)] | Auto generated |
| Sorting network for 6 inputs, 12 CEs, 5 layers. Worst case 8 swaps, 4.7 swaps on average. [(0,5),(1,3),(2,4)] | Auto generated |
| Sorting network for 7 inputs, 16 CEs, 6 layers. Worst case 11 swaps, 5.89047619 swaps on average. [(0,6),(1,5),(2,3)] | Auto generated |
| Sorting network for 8 inputs, 19 CEs, 6 layers. Worst case 14 swaps, 7.94285714 swaps on average. [(0,7),(1,6),(2,5),(3,4)] | Auto generated |
| Sorting network for 9 inputs, 25 CEs, 7 layers. Worst case 17 swaps, 9.02539683 swaps on average. [(0,8),(1,6),(2,5),(4,7)] | Auto generated |
| Sorting network for 10 inputs, 29 CEs, 8 layers. Worst case 21 swaps, 10.77619048 swaps on average. [(0,7),(1,6),(2,9),(3,8),(4,5)] | Auto generated |
| Sorting network for 11 inputs, 35 CEs, 8 layers. Worst case 23 swaps, 13.10577201 swaps on average. [(0,9),(1,7),(3,10),(4,5),(6,8)] | Auto generated |
| Sorting network for 12 inputs, 39 CEs, 9 layers. Worst case 27 swaps, 14.60606061 swaps on average. [(0,11),(1,10),(2,9),(3,8),(4,7),(5,6)] | Auto generated |
| Sorting network for 13 inputs, 45 CEs, 10 layers. Worst case 32 swaps, 16.91999112 swaps on average. [(0,12),(1,11),(2,10),(3,7),(4,9),(5,6)] | Auto generated |
| Sorting network for 14 inputs, 51 CEs, 10 layers. Worst case 35 swaps, 19.88281718 swaps on average. [(0,13),(1,12),(2,11),(3,10),(4,9),(5,8),(6,7)] | Auto generated |
| Sorting network for 15 inputs, 56 CEs, 10 layers. Worst case 41 swaps, 21.45675436 swaps on average. [(0,13),(1,14),(2,8),(3,10),(4,7),(5,9),(6,12)] | Auto generated |
| Sorting network for 16 inputs, 60 CEs, 10 layers. Worst case 46 swaps, 23.86853147 swaps on average. [(0,15),(1,14),(2,13),(3,12),(4,11),(5,10),(6,9),(7,8)] | Auto generated |
| 2024-05-19 | Lower worst case swap count for 11, 14 and 15 inputs. Optimized average swaps for 13 and 16 inputs. |
| 2024-05-01 | Initial list |
Page updated on Sun May 19 15:17:17 2024
See SorterHunter repo for previous versions.