Sorting network

From Wikipedia, the free encyclopedia
Jump to: navigation, search
A simple sorting network consisting of four wires and five connectors

A sorting network is a mathematical model of a network of wires and comparator modules that is used to sort a sequence of numbers. Each comparator connects two wires and sorts the values by outputting the smaller value to one wire, and the larger to the other. The main difference between sorting networks and comparison sorting algorithms is that with a sorting network the sequence of comparisons is set in advance, regardless of the outcome of previous comparisons. This independence of comparison sequences is useful for parallel execution of the algorithms. Despite the simplicity of the model, sorting network theory is surprisingly deep and complex. These networks were first studied circa 1954 by Armstrong, Nelson and O'Connor,[1] who subsequently patented the idea.[2]

Sorting networks can be implemented either in hardware or in software. Donald Knuth describes how the comparators for binary integers can be implemented as simple, three-state electronic devices.[1] Batcher, in 1968, suggested using them to construct switching networks for computer hardware, replacing both buses and the faster, but more expensive, crossbar switches.[3] Since the 2000s, they are used (especially bitonic mergesort) by the GPGPU community for constructing sorting algorithms to run on graphics processing units.[4]

Introduction[edit]

Demonstration of a comparator in a sorting network.

A sorting network consists of two types of items: comparators and wires. The wires are thought of as running from left to right, carrying values (one per wire) that traverse the network all at the same time. Each comparator connects two wires. When a pair of values, traveling through a pair of wires, encounter a comparator, the comparator swaps the values if and only if the top wire's value is greater than the bottom wire's value.

In a formula, if the top wire carries x and the bottom wire carries y, then after hitting a comparator the wires carry x' = \min(x, y) and y' = \max(x, y), respectively, so the pair of values is sorted.[5]:635 A network of wires and comparators that will correctly sort all possible inputs into ascending order is called a sorting network.

The full operation of a simple sorting network is shown below. It is easy to see why this sorting network will correctly sort the inputs; note that the first four comparators will "sink" the largest value to the bottom and "float" the smallest value to the top. The final comparator simply sorts out the middle two wires.

SimpleSortingNetworkFullOperation.svg

Depth and efficiency[edit]

The efficiency of a sorting network can be measured by its total size, the number of comparators used, or by its depth, defined (informally) as the largest number of comparators that any input value can encounter on its way through the network. 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.[5]:636–637

Insertion and selection networks[edit]

We can easily construct a network of any size recursively using the principles of insertion and selection. Assuming we have a sorting network of size n, we can construct a network of size n + 1 by "inserting" an additional number into the already sorted subnet (using the principle behind insertion sort). We can also accomplish the same thing by first "selecting" the lowest value from the inputs and then sort the remaining values recursively (using the principle behind bubble sort).

A sorting network constructed recursively that first sinks the largest value to the bottom and then sorts the remaining wires. Based on bubble sort
A sorting network constructed recursively that first sorts the first n wires, and then inserts the remaining value. Based on insertion sort

The structure of these two sorting networks are very similar. A construction of the two different variants, which collapses together comparators that can be performed simultaneously shows that, in fact, they are identical.[1]

Bubble sorting network
Insertion sorting network
When allowing for parallel comparators, bubble sort and insertion sort are identical

The insertion network has a large depth of 2n - 3,[1] making it impractical. Better constructions are discussed below.

Zero-one principle[edit]

While it is easy to prove the validity of some sorting networks (like the insertion/bubble sorter), it is not always so easy. There are n! 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. The number of test cases can be reduced significantly, to 2n, using the so-called zero-one principle. While still exponential, this is smaller than n! for all n >= 4, and the difference grows rapidly with increasing n.

The zero-one principle states that, if a sorting network can correctly sort all 2n sequences of zeros and ones, then it is also valid for arbitrary ordered inputs. This not only drastically cuts down on the number of tests needed to ascertain the validity of a network, it is of great use in creating many constructions of sorting networks as well.

The principle can be proven by first observing the following fact about comparators: when a monotonic function f is applied to the inputs, i.e., x and y are replaced by f(x) and f(y), then the comparator produces \min(f(x), f(y)) = f(\min(x, y)) and \max(f(x), f(y)) = f(\max(x, y)). By induction on the depth of the network, this result can be extended to a lemma stating that if the network transforms the sequence a1, ..., an into b1, ..., bn, it will transform f(a1), ..., f(an) into f(b1), ..., f(bn). The proof now proceeds by contradiction: suppose that some input a1, ..., an contains two items ai < aj, and the network incorrectly swaps these in the output. Then it will also incorrectly sort f(a1), ..., f(an) for the function


f(x) = \begin{cases}
        1 \textrm{ if } x > a_i \\
        0 \textrm{ otherwise.}
       \end{cases}

This function is monotonic, so we have the zero-one principle as the contrapositive.[5]:640–641

The principle has been proven by a special case of a 1954 theorem due to W. G. Bouricius.[1][clarification needed]

Constructing sorting networks[edit]

Various algorithms exist to construct simple, yet efficient sorting networks of depth O(\log^2n) (hence size O(n\log^2n)) such as Batcher odd–even mergesort, bitonic sort, Shell sort, and the Pairwise sorting network. These networks are often used in practice. It is also possible, in theory, to construct networks of logarithmic depth for arbitrary size, using a construction called the AKS network, after its discoverers Ajtai, Komlós, and Szemerédi.[6] While an important theoretical discovery, the AKS network has little or no practical application because of the linear constant hidden by the Big-O notation, which is in the "many, many thousands".[5]:653 These are partly due to a construction of an expander graph. A simplified version of the AKS network was described by Paterson, who notes that "the constants obtained for the depth bound still prevent the construction being of practical value".[7] Another construction of sorting networks of size O(n\log n) was discovered by Goodrich.[8] While their size has a much smaller constant factor than that of AKS networks, their depth is O(n\log n), which makes them inefficient for parallel implementation.

Optimal sorting networks[edit]

For small, fixed numbers of inputs n, optimal sorting networks can be constructed, with either minimal depth (for maximally parallel execution) or minimal length (number of comparators). These networks can be used to increase the performance of larger sorting networks resulting from the recursive constructions of, e.g., Batcher, by halting the recursion early and inserting optimal nets as base cases.[9] The following table summarizes the known optimality results:

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Depth[10] 0 1 3 3 5 5 6 6 7 7 8 8 9 9 9 9
Length, upper bound[11] 0 1 3 5 9 12 16 19 25 29 35 39 45 51 56 60
Length, lower bound (if different)[11] 33 37 41 45 49 53

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[10] (the cases nine and ten having been decided in 1991[9]).

For one to ten inputs, length-optimal sorting networks are known, and for higher values, lower bounds on their lengths S(n) can be derived inductively using a lemma due to Van Voorhis: S(n + 1) ≥ S(n) + ⌈log2(n)⌉. All ten optimal networks have been known since 1969, with the first eight again being known as optimal since the work of Floyd and Knuth, but optimality of the cases n = 9 and n = 10 took until 2014 to be resolved.[11]

Some work in designing optimal sorting network has been done using genetic algorithms.[12][better source needed]

Complexity of testing sorting networks[edit]

It is unlikely that significant further improvements can be made for testing general sorting networks, unless P=NP, because the problem of testing whether a candidate network is a sorting network is known to be co-NP-complete.[13]

References[edit]

  1. ^ a b c d e f Knuth, D. E. (1997). The Art of Computer Programming, Volume 3: Sorting and Searching (Third Edition ed.). Addison–Wesley. pp. 219–247. ISBN 0-201-89685-0.  Section 5.3.4: Networks for Sorting.
  2. ^ US 3029413, O'Connor, Daniel G. & Nelson, "Sorting system with n-line sorting switch", published 10 April 1962 
  3. ^ Batcher,, K. E. (1968). "Sorting networks and their applications". Proc. AFIPS Spring Joint Computer Conference. pp. 307–314. 
  4. ^ Owens, J. D.; Houston, M.; Luebke, D.; Green, S.; Stone, J. E.; Phillips, J. C. (2008). "GPU Computing". Proceedings of the IEEE 96 (5): 879. doi:10.1109/JPROC.2008.917757.  edit
  5. ^ a b c d Cormen, Thomas H.; Leiserson, Charles E., Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8. 
  6. ^ Ajtai, M.; Komlós, J.; Szemerédi, E. (1983). "An O(n log n) sorting network". "Proc. 15th Annual ACM Symp. on the Theory of Computing (STOC)". pp. 1–9. doi:10.1145/800061.808726. ISBN 0897910990.  edit
  7. ^ Paterson, M. S. (1990). "Improved sorting networks with O(log N) depth". Algorithmica 5: 75–92. doi:10.1007/BF01840378.  edit
  8. ^ Goodrich, Michael (March 2014). "Zig-zag Sort: A Simple Deterministic Data-Oblivious Sorting Algorithm Running in O(n log n) Time". arXiv:1403.2777 [cs.DS].
  9. ^ a b Parberry, Ian (1991). "A Computer Assisted Optimal Depth Lower Bound for Nine-Input Sorting Networks". Mathematical Systems Theory 24: 101–116. 
  10. ^ a b Bundala, D.; Závodný, J. (2014). "Optimal Sorting Networks". "Language and Automata Theory and Applications". Lecture Notes in Computer cience 8370. p. 236. arXiv:1310.6271. doi:10.1007/978-3-319-04921-2_19. ISBN 978-3-319-04920-5. 
  11. ^ a b c Codish, Michael; Cruz-Filipe, Luís; Frank, Michael; Schneider-Kamp, Peter (2014). "Twenty-Five Comparators is Optimal when Sorting Nine Inputs (and Twenty-Nine for Ten)". arXiv:1405.5754 [cs.DM].
  12. ^ Mitchell, M. (1998). An Introduction to Genetic Algorithms. MIT Press. pp. 21–27. ISBN 0-262-63185-7. 
  13. ^ Parberry, Ian (1991). "On the Computational Complexity of Optimal Sorting Network Verification". Proc. PARLE '91: Parallel Architectures and Languages Europe, Volume I: Parallel Architectures and Algorithms, Eindhoven, The Netherlands: 252–269. 

External links[edit]