Channels ▼
RSS

Sorting Networks


February 1993/Sorting Networks

Frederick Hegeman is an amateur programmer and computer language hobyist. He can be reached at P.O. Box 2368, Rapid City, SD 57709, telephone (605) 343-7014.

A sorting network sorts n items by performing a predetermined set of comparisons. A software implementation for a sequential computer might take the form

swap(1,2); swap(4,5); swap(3,5);
swap(3,4); swap(1,4); swap(1,3);
swap(2,5); swap(2,4); swap(2,3);
where swap(a,b) = if(b < a) exchange a and b;
This is a nine-comparison network for sorting five items. You might try it with pennies, nickels, dimes, quarters, and cheeseburgers. The best-, worst-, and typical-case number of comparisons are the same. Only the number of exchanges varies. Nine comparisons are, in fact, the fewest necessary to sort five items by exchanges when any combination of items is possible. When n is known to be small, these simple predetermined sequences out-perform the best algorithmic sorts.

In theory, the minimum number of comparisons necessary to sort n items is the ceiling of log2(n!). As n grows larger, 1og2(n!) approaches nlog2(n). The reason why O(nlog2(n)) sorting algorithms, such as Quicksort, are so efficient as n grows larger should be obvious. Sorting networks generated by the Bose-Nelson algorithm (See Listing 1. ) are O(n1.585), which diverges from nlog2(n) rapidly. However, the Bose-Nelson network for 16 elements is 65 comparisons, which is pretty nearly nlog2(n), and sorting 1000 random 16-element arrays using a Quicksort that pivoted on the last element in the array requires 85.43 comparisons on average, which is just over n1.585. This is probably the reverse of what you might have expected. Sorting is so often discussed in terms of increasing n that it is easy to fall into the trap of expecting "efficient" algorithms to behave nicely over the whole range of their inputs. The "gotcha" in Quicksort is the extra comparisons needed to properly partition the array. They are insignificant when sorting a large array but constitute a significant part of the total when the array is small. As n becomes very small, the behavior of sorting networks comes closer to the ideal.

Bose-Nelson generates minimum comparison networks only for n <= 8. However, minimum comparison networks are available for 9 <=n<=16 as well. Those generated by the code in Listing 2 are based on illustrations in The Art of Computer Programming, Vol. 3 (Knuth 1973). Please note that both listings generate sorts according to element numbers — one greater than the corresponding array index.

Sorting small arrays is a problem all its own, difficult to understand in the usual terms. If you need to sort a small array in a time-critical section of code, you can count on only two things holding true: your algorithmic sort may perform much worse than expected, and no algorithmic sort can match the minimum comparison networks on all combinations of elements. When that code is part of something like an operating system, the networks have at least two other attractive features: many comparisons can be done in parallel, if appropriate; and they are inherently re-entrant, so that sorting may be interleaved with other tasks.

Bibliography

Knuth, Donald E. 1973. The Art of Computer Programming, Vol. 3. Reading, MA: Addison-Wesley. Pp. 220-229.

Bose, R. C. and Nelson, R. J. 1962. "A Sorting Problem". JACM, Vol. 9. Pp. 282-296.

Davis, Wilbon. September, 1992. "Time Complexity". The C Users Journal, Vol. 10, No. 9. Pp. 29-38.


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 

Video