Stephen Wolfram's: A New Kind of Science | Online
Jump to Page
Look Up in Index

Chapter 12 Notes > Section 8 > Page 1142 > Note (a) Previous note-----Next note
Notes for: The Principle of Computational Equivalence | Undecidability and Intractability

*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, 2^t, 2^(i + 1) - 2^t]}, Map[
{0, d} + #1 &, Select[Range[n - d], BitAnd[#1 - 1, 2^t] ==
If[i == m, 0, 2^t] &]]], {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 2^n 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.)


Page image


Pages related to this note:


All notes on this page:

* [Classes of] fast algorithms
* Sorting networks
* Computational complexity theory
* All notes for this section
* Downloadable programs for this page
* Downloadable images
* Search Forum for this page
* Post a comment
* NKS | Online FAQs
From Stephen Wolfram: A New Kind of Science [citation] Previous note-----Next note