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)
- Instructions for Sorting Networks activity (English)
- Italian Language Version
- French Language Version
- Turkish Language Version
- Greek Language Version
- Portugese (Brazil) Language Version
- Polish Language Version
- Slovenian Language Translation
- Vladimir Estivill-Castro has developed an interactive online game-like activity for students to explore sorting networks, using cows and railway tracks!
- CS Bits & Bytes use the parallel sorting network activity to illustrate multicore computers. The activity uses a serial and parallel 4-way sorting network.
- National Center for Women & Information Technology (NCWIT) has a learning package called Unplugged in a Box which has detailed lesson plan of an activity called “Beat the Clock”.Download the related video at Beat the Clock — Sorting Networks
- Mordechai (Moti) Ben-Ari from the Weizmann Institute of Science, Israel has programmed the Sorting Networks Unplugged activity in Scratch which can be downloaded in a zip file of the complete set of activities. Please read the ReadMe.txt for documentation.
- The Greenroom resources area using the Greenfoot software has the sorting network solved you can download and use in the Greenfoot environment.
If you are a teacher, you can apply easily to join and use the resources there.
- 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 thorugh 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.
- Hiroki Manabe has created a Flash animation version of the Sorting Networks activity
- 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.
- Wikipedia: Sorting Network
- The Mathmaniacs web site has a similar activity (lesson 9)
- For sorting networks of different sizes, there is a website that can generate them for you at http://pages.ripco.net/~jgamble/nw.html. It uses a slightly different notation, which is explained in the Wikipedia entry
- Michele Fini from Italy does the Sorting Network activity with his 11 and 12 year olds class in the following Video: Sorting Networks Race (gara di ordinamento)
- The paper Interactive Learning of Algorithms, by Jarmo Rantakokko, evaluates teaching parallel sorting algorithms (not sorting networks) using animation. It provides some nice ways to visualise other algorithms, and also discusses the benefit of animation and kinesthetic activities compared with text book descriptions.
- University of Tennessee Department of Computer Science has an introductory CS module intended to teach Networks and the Internet using animation. Note: This site is best viewed in Internet Explorer.
- The “Hot Wheels 4-lane elimination race” has a mechanism that lets the fastest car of each pair through, which forms a network equivalent to the adaptation of the sorting network for finding the maximum value. (It’s also equivalent to a tournament tree).
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.
- In 2005, a demonstration video for sorting networks shows 21 students making and using a sorting network (near the end of the video).
Great Principles of Computer Science [info]
New Zealand Curriculum [info]Expand
- Technology Level 1: Planning for Practice
- Outline a general plan to support the development of an outcome, identifying appropriate steps and resources
- Technology Level 1: Characteristics of technological outcomes
- Understand that technological outcomes are products or systems developed by people and have a physical nature and a functional nature.
- Technology Level 1:Technological systems
- Understand that technological systems have inputs, controlled transformations, and outputs.