Activity 8

Beat the Clock—Sorting Networks

Summary

Computers are very fast. But even fast computers have limits. One way to make things faster is to use many computers at once. Each computer works on a different part of the job.

In this activity, we use something called a sorting network. A sorting network is a special path that puts numbers in order. It can check many numbers at the same time.

Skills You Will Use

• Comparing numbers
• Putting things in order
• Making step-by-step plans (called algorithms)
• Working together to solve problems

Ages

7 years and up

What You Need

This is an outdoor group game.

• Chalk
• Two sets of six cards (numbered)
• A stopwatch

---

Sorting Networks

Before you start, use chalk to draw a network (a path with lines and circles) on the ground.

Instructions for Children

This activity shows how computers put jumbled-up numbers in order using a sorting network.

1. Get into groups of six. Only one group uses the network at a time.
2. Each person takes a numbered card.
3. Each person stands in a square on the left side of the court (this is the "IN" side). Your numbers should be mixed up, not in order.
4. Walk along the lines on the ground. When you reach a circle, stop and wait for someone else to arrive there too.
5. When another person arrives at your circle, compare cards. Whoever has the smaller number takes the path on the left. Whoever has the bigger number takes the path on the right.
6. When you reach the other end, check: are you in the correct order?

If your group makes a mistake, start again from the beginning. Make sure everyone understands how a circle (called a node) works: the smaller number always goes left, and the bigger number always goes right.

---

Variations (Ways to Change the Game)

1. Once everyone knows how to play, use a stopwatch. Time how long each group takes to finish the network.
2. Try using cards with bigger numbers, like numbers with three digits.
3. Try even bigger numbers that are harder to compare. Or use words and put them in alphabetical order (A to Z) instead.

Extra Challenges

1. What if you switch the rule? What happens if the smaller number goes right instead of left? (The numbers will end up in the opposite order — biggest to smallest instead of smallest to biggest.)

What if you run the network backwards? (It won't always work! Try to find an example where the numbers come out in the wrong order.)

1. Try to design your own sorting network, either smaller or bigger than this one.

1. Compare two different networks that both sort four numbers. Which one is faster? One network makes you do all the comparisons one at a time (this is called serial processing). The other network lets you do some comparisons at the same time (this is called parallel processing). The one that does things at the same time is faster!

1. Try building an even bigger sorting network.

1. Networks can also help you find the smallest or biggest number in a group. For example, a network with eight numbers going in can be built so that only the smallest number comes out at the end.

1. Think about everyday jobs. Which ones get faster if more people help? Which ones don't? For example, cooking a meal is much slower if you only have one stove burner — you'd have to cook everything one at a time. But some jobs can be split up between many people to finish faster. Can you think of jobs that can't be sped up this way, no matter how many people help?

---

What's It All About?

As we use computers more, we want them to work faster.

One way to make a computer faster is to write instructions that use fewer steps. (You may remember this idea from other activities.)

Another way is to use several computers at once, each working on a different part of the same job.

For example, in the six-number sorting network, there are 12 comparisons in total. But since up to three comparisons can happen at the same time, the whole job only takes as long as 5 steps. This "working together at the same time" method (called parallel processing) sorts the numbers more than twice as fast as doing one comparison at a time.

But not every job gets faster with more helpers. Here's an example: imagine one person digging a ditch that is ten meters long. If ten people each dig one meter, the job finishes much faster.

But now imagine a ditch that is ten meters deep. You can't have ten people dig at once, because no one can reach 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 split up problems, so that many computers can solve them together — at the same time.