A sorting network for permutations of length 7

3 October 2026

For the #Mathober 2026 day 3 prompt ‘Permutation list’, I offer a diagram demonstrating the functioning of a minimal sorting network for permutations of length 7.

Illustration of how the permutation (6,4,2,0,1,3,5) is sorted by a network with 16 comparators. The permutation passes from left to right through the comparators, each of which compares two elements and interchanges them if necessary. The paths taken by each element are traced from left to right.

Each of the 16 comparators interchanges two elements if they are not ordered correctly.

Sixty years ago, in what was possibly the first-ever computer-assisted proof, R. W. Floyd & D. E. Knuth established that 16 is the minimum number of comparators required for a single network to sort any permutation of length 7.1

Notes

  1. R. W. Floyd & D. E. Knuth, ‘The Bose-Nelson Sorting Problem’. ch. 15, pp. 163-172 in: J. N. Srivastava, F. Harary, C. R. Rao, G.-C. Rota & S. S. Shrikhande, eds, A Survey of Combinatorial Theory. Amsterdam, London & New York: North-Holland & Elsevier, 1973. ISBN: 978-0-7204-2262‑7. Theorem 5. ↩

Image source

«
Periodic solutions of the three-body problem
Copyright 2025–6 Alan J. Cain.
Licensed under the Creative Commons Attribution–Non-Commercial–NoDerivs 4.0 International Licence.