Sorting Networks

Beat the Clock #

To make computers go faster, it can be a lot more effective to have several slower computers working on a problem than a single fast one. This raises questions about how much of the computation can be done at the same time.

Here we use a fun team activity to demonstrate an approach to parallel sorting. It can be done on paper, but we like to get students to do it on a large scale, running from node to node in the network.

Activity description (PDF) #

Translations and other versions #

Videos #

See our video page.

Extensions #

  • As an extra challenge for the children, have them do the activity completely silently
  • Use words (compared using dictionary order) instead of numbers for sorting. This will generally slow the children down, especially if some words start with the same letters
  • This is a good exercise for thinking about permutations. For example, with 6 people entering the sorting network, there are 6x5x4x3x2x1=720 possible orders that they can start in, yet only one way that they will come out. When children are designing their own sorting networks, they should test them with all possibly input patterns. For example, to check a 3-input sorting network, there are 6 (3x2x1) possible input permutations, and for 4 inputs there are 24 (4x3x2x1) permutations, and for n inputs there are n! (factorial) permutations. These numbers get larger very rapidly
  • Jeff Gray from University of Alabama at Birmingham has the following suggestion as an extension to this activity using robotics:
    • Place the robots on an initial position in a sorting network.
    • Have each robot generate a random number
    • Have the robots do the pairwise comparison through Bluetooth using unique identifiers of each robot
    • Coordination of “Traffic” will be needed so the robots can move across the network so that they do not bump into each other.

Photos #

An older version of this activity can be downloaded in PDF format here. The content is similar to the current version, but there’s some extra technical information.

More lessons and activities #

If you want to find out more #

Videos #

Additional resources #

Sorting network records #

Although the 6-input sorting network is about right for working with the concepts, there’s no limit on the size of the network, although it can get large very quickly! The follow examples show some larger sorting network activities:

Around 1999 at the Siemens Science School, University of Canterbury, a sorting network of about 25 students

Around 1999 at the Siemens Science School, University of Canterbury, a sorting network of about 25 students

In 2005, a demonstration video for sorting networks shows 21 students making and using a sorting network (near the end of the video)

In 2005, a demonstration video for sorting networks shows 21 students making and using a sorting network (near the end of the video)

In September 2019, 50 pupils from high schools in Vienna, performed a sorting network, which is based on the data available on the CS Unplugged classic, one of the largest ones ever performed

In September 2019, 50 pupils from high schools in Vienna, performed a sorting network, which is based on the data available on the CS Unplugged classic, one of the largest ones ever performed

Great Principles of Computer Science #

  • Computation