Sorting network

Sorting networks were first studied circa 1954 by Armstrong, Nelson and O'Connor,[1] who subsequently patented the idea.

Donald Knuth describes how the comparators for binary integers can be implemented as simple, three-state electronic devices.

Noting that sorting networks can perform certain comparisons in parallel (represented in the graphical notation by comparators that lie on the same vertical line), and assuming all comparisons to take unit time, it can be seen that the depth of the network is equal to the number of time steps required to execute it.

A construction of the two different variants, which collapses together comparators that can be performed simultaneously shows that, in fact, they are identical.

This is better than the O(n log n) time needed by random-access machines, but it turns out that there are much more efficient sorting networks with a depth of just O(log2 n), as described below.

permutations of numbers in an n-wire network, and to test all of them would take a significant amount of time, especially when n is large.

Suppose that some input a1, ..., an contains two items ai < aj, and the network incorrectly swaps these in the output.

[6] While an important theoretical discovery, the AKS network has very limited practical application because of the large linear constant hidden by the Big-O notation.

A simplified version of the AKS network was described by Paterson in 1990, who noted that "the constants obtained for the depth bound still prevent the construction being of practical value".

[7] A more recent construction called the zig-zag sorting network of size O(n log n) was discovered by Goodrich in 2014.

[8] While its size is much smaller than that of AKS networks, its depth O(n log n) makes it unsuitable for a parallel implementation.

The bounds known so far are provided in the table below: The first sixteen depth-optimal networks are listed in Knuth's Art of Computer Programming,[1] and have been since the 1973 edition; however, while the optimality of the first eight was established by Floyd and Knuth in the 1960s, this property wasn't proven for the final six until 2014[15] (the cases nine and ten having been decided in 1991[9]).

For one to twelve inputs, minimal (i.e. size-optimal) sorting networks are known, and for higher values, lower bounds on their sizes S(n) can be derived inductively using a lemma due to Van Voorhis[1] (p. 240): S(n) ≥ S(n − 1) + ⌈log2n⌉.