Sorting networks
Any list can be sorted using Fold[PairSort, list, pairs] by doing a fixed sequence of comparisons of pairs
PairSort[a_, p : {_, _}] := Block[{t = a}, t〚p〛 = Sort[t〚p〛]; t]
(Different comparisons often do not interfere and so can be done in parallel.) The pictures below show a few sequences of pair comparisons that sort lists of length n = 16.
The top two (both with 120 comparisons) have a repetitive structure and correspond to standard sorting algorithms: transposition sort and insertion sort. (Quicksort does not use a fixed sequence of comparisons.) The first one on the bottom (with 63 comparisons) has a nested structure and uses the method invented by Kenneth Batcher in 1964:
Flatten[Reverse[Flatten[With[{m = Ceiling[Log[2, n]] - 1}, Table[With[{d = If[i m, 2t, 2i + 1 - 2t]}, Map[{0, d} + # &, Select[Range[n - d], BitAnd[# - 1, 2t] If[i m, 0, 2t] &]]], {t, 0, m}, {i, t, m}]], 1]], 1]
The second one on the bottom also uses 63 comparisons, while the last one is the smallest known for n = 16: it uses 60 comparisons and was invented by Milton Green in 1969. For n ≤ 16 the smallest numbers of comparisons known to work are {0, 1, 3, 5, 9, 12, 16, 19, 25, 29, 35, 39, 45, 51, 56, 60}. (In general all lists will be sorted correctly if lists of just 0's and 1's are sorted correctly; allowing even just one of these 2n cases to be wrong greatly reduces the number of comparisons needed.) For n ≤ 8 the Batcher method is known to give minimal length sequences of comparisons (for n ≤ 5 the total numbers of minimal sequences that work are {1, 6, 3, 13866}). The Batcher method in general requires about n Log[n]2 comparisons; it is known that in principle n Log[n] are sufficient. Various structures such as de Bruijn and Cayley graphs can be used as the basis for sorting networks, though it is my guess that typically the smallest networks for given n will have no obvious regularity. (See also page 832.)