Activity 8

Beat the Clock—Sorting Networks

Summary

Computers are fast, but there's still a limit to how quickly they can solve problems. One way to speed things up is to use several computers to work on different parts of a problem at the same time. In this activity, we use sorting networks—systems that let several sorting comparisons happen simultaneously (at once) instead of one after another.

Curriculum Links

• Mathematics: Number level 2 and up. Exploring number: greater than, less than

Skills

• Comparing
• Ordering
• Developing algorithms (step-by-step methods for solving a problem)
• Co-operative problem solving

Ages

7 years and up

Materials

This is an outdoor group activity. You will need:

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

---

Sorting Networks

Before you begin, use chalk to mark out the network pattern on a court or playground.

Instructions for Children

This activity will show you how computers sort random numbers into order using something called a sorting network.

1. Get into groups of six. Only one team uses the network at a time.
2. Each team member takes a numbered card.
3. Stand in a square on the left-hand (IN) side of the court. Your numbers should be mixed up, not in order.
4. Walk along the marked lines. When you reach a circle, wait there until another team member arrives.
5. When someone else arrives at your circle, compare cards. Whoever has the smaller number takes the exit to the left. Whoever has the larger number takes the exit to the right.
6. Once everyone reaches the other end of the court, check: are you now standing in the correct order?

If a team makes a mistake, they must start over. Make sure everyone understands how a "node" (circle) works: the smaller number always goes left, and the larger number always goes right.

---

Variations

1. Once the children know the activity well, use a stopwatch to time how long each team takes to get through the network.
2. Use cards with bigger numbers (like the three-digit numbers on the photocopy master).
3. Create cards with even larger numbers that take more effort to compare—or use words and sort them alphabetically instead.

Extension Activities

1. What if you switched the rule—smaller numbers go right and larger numbers go left? (The numbers will end up sorted in reverse order.)

Does the network still work if used backwards? (Not necessarily—see if you can find an example where a number comes out in the wrong place.)

1. Try designing your own sorting networks, smaller or larger than this one. For example, there's a network that can sort just three numbers—see if you can figure out its design yourself.

1. Below are two different networks that can each sort four numbers. Which one works faster? (The second network is faster. In the first network, every comparison must happen one after another—this is called serial processing. In the second network, some comparisons can happen at the same time—this is called parallel processing, and it lets the network finish faster.)

1. Try building an even larger sorting network.

1. Networks can also be used to find just the minimum (smallest) or maximum (largest) value among a set of numbers. For example, a network with eight inputs can be built so that only one output remains—the smallest number—while the rest of the values simply end at dead ends in the network.

1. Think about everyday tasks: which ones can be sped up by having more people work at the same time, and which ones can't? For example, cooking a meal is much slower if you only have one burner, since everything has to be cooked one dish at a time instead of all together. What other jobs get faster 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 quickly as possible.

One way to make a computer faster is to write programs that use fewer steps (as we saw in Activities 6 and 7).

Another way to solve problems faster is to have several computers work on different parts of the same task at the same time. For example, in the six-number sorting network, a total of 12 comparisons are needed to sort the numbers—but up to three comparisons can happen simultaneously. This means the whole task only takes as long as 5 comparison "rounds," rather than 12. This parallel network sorts the list more than twice as fast as a system that can only do one comparison at a time.

However, not every task can be sped up this way. Here's an analogy: imagine one person digging a ditch that is ten meters long. If ten people each dug one meter of the ditch, the job would be finished much faster. But that same trick wouldn't work for a ditch that is ten meters deep—you can't start digging the second meter down until the first meter has already been dug. Computer scientists are still working hard to figure out the best ways to break big problems into smaller pieces so that many computers can solve them together, in parallel.