Activity 8

Beat the Clock—Sorting Networks

Summary

Computers are fast, but they aren't infinitely fast — there's a limit to how quickly they can solve problems. One way to speed things up is to divide the work among several computers, each handling a different part of the task. In this activity, you'll explore sorting networks, systems that carry out multiple sorting comparisons at the same time (in parallel) rather than one at a time.

Curriculum Links

• Mathematics: Number, Level 2 and up. Understanding number relationships — greater than, less than.

Skills

• Comparing
• Ordering
• Building algorithms (step-by-step problem-solving procedures)
• Working together to solve problems

Ages

7 years and up

Materials

This is an outdoor group activity. You'll need:

• Chalk
• Two sets of six numbered cards (copy the Photocopy Master "Sorting Networks" onto card stock and cut them out)
• A stopwatch

---

Setting Up

Before starting, use chalk to draw the sorting network pattern on a court or playground surface.

Instructions for Students

This activity demonstrates how computers can sort a random set of numbers using a sorting network.

1. Form groups of six. Only one group uses the network at a time.
2. Each person in the group takes one numbered card.
3. Everyone stands in a square on the left-hand ("IN") side of the court. The numbers should be arranged in random, mixed-up order.
4. Walk along the marked lines. Each time you reach a circle, stop and wait for someone else to arrive there too.
5. When another team member reaches your circle, compare your cards. Whoever has the smaller number takes the exit on their left; whoever has the larger number takes the exit on their right.
6. Once everyone reaches the far end of the court, check: are the numbers now in the correct order?

If a team makes a mistake, they must start over. Before beginning, make sure everyone understands how a "node" (circle) works: the smaller value always exits left, and the larger value always exits right.

---

Variations

1. Once students are comfortable with the activity, use a stopwatch to time how long each team takes to pass through the entire network.
2. Try using cards with larger numbers (such as the three-digit numbers included in the photocopy master).
3. Create cards with even bigger numbers that require more effort to compare — or use words and compare them alphabetically instead.

Extension Activities

1. Reverse the rule: What happens if the smaller number goes right instead of left, and the larger number goes left instead of right? (The final numbers will end up sorted in reverse order.)

Run it backwards: Does the network still work correctly if used in reverse? (Not necessarily — students should be able to find an example where numbers come out in the wrong order.)

1. Try designing smaller or larger networks. For example, there's a network that can sort just three numbers — see if students can figure out its design on their own.

1. Below are two different networks, each capable of sorting four numbers. Which one is faster?

(The second network is faster. The first requires every comparison to happen one after another — this is called serial processing. The second network allows some comparisons to happen at the same time — this is parallel processing — which makes it quicker overall.)

1. Try building an even larger sorting network.

1. Networks can also be designed to find just the minimum or maximum value among a set of inputs. For example, an eight-input network can be built so that only one output — the minimum value — comes through, while the rest of the values get left behind at dead ends within the network.

1. Think about everyday tasks: which ones can be sped up by having multiple people work on them at once (parallelism), and which ones can't? For instance, cooking a meal would take much longer with only one burner, since each dish would have to be cooked one at a time instead of simultaneously. What other jobs speed up when more people help? What jobs don't?

---

What's It All About?

As we rely on computers more and more, we want them to process information as fast as possible.

One way to speed up a computer is to write programs that require fewer computational steps (as seen in Activities 6 and 7).

Another way to solve problems faster is to have multiple computers work on different parts of the same task simultaneously. Take the six-number sorting network as an example: sorting the numbers requires a total of 12 comparisons, but because up to three comparisons happen at the same time, the whole process only takes as long as 5 comparison steps would take individually. This parallel network sorts the list more than twice as fast as a system limited to performing one comparison at a time.

However, not every task benefits from parallel processing. Consider this analogy: if one person needs to dig a ten-meter-long ditch, having ten people each dig a one-meter section would finish the job much faster. But this strategy wouldn't work for a ditch that needs to be dug ten meters deep — you can't start digging the second meter down until the first meter has been completed. Computer scientists continue to search for the best ways to break problems into pieces that can be solved efficiently by computers working in parallel.