Motivation:

Materials:

1. Sorting network either drawn with chalk outside, or with painter's tape inside, or on a tarp (picture, picture)
2. Four-item sorting net placemats and numbered chips to sort.
3. Three item sort worksheet (incorrect 3-sorter).
4. Parallel adding challenge exercise.

Lesson Plan:

1. First get the students familiar with the operations of the sorting net by having them sort themselves on the 6-sorter network (tarp or chalk).
2. Decide ahead of time what kinds of things you would like to sort. For an icebreaker or for practice in alphabetizing, use the students' names. For an exercise in numerical comparisons use whole numbers, decimals, fractions, or whatever you'd like.
3. Assign each student a number or word to be sorted, or have them come up with their own. Have them write the number or object to be sorted on a piece of paper. You may want to attach the numbers to the children somehow. This activity works best if the values to be sorted are unique, so make sure the children all have different numbers. You may want to let kids see what happens if some of the values are the same.
4. The students start at the squares at the beginning of the network in random order. They advance along the marked lines, and when they arrive at a comparison node they wait for someone else to arrive. After comparing their values, the person with the smaller value (or first alphabetically) exits to the left, and the other to the right. Depending on the size of your network, you may have to take students in groups. This activity may also be done as a race, where each group's network traversal is timed. Whether racing or not, students will have a tendency to rush ahead, so it is important to stress the necessity of waiting at each comparison node until TWO people have shown up there - only then may either or them proceed.
5. When they've arrived at the end of the network, have them verify that they are indeed in order.
6. Discussion (can be done later): "How did this happen?" Someone will say that it happened because they compared themselves with each other. Make sure they notice, however, that each of them did NOT compare him/herself with EVERY other person! (Chances are that they'll figure this out themselves.) If appropriate, this is a good time to discuss the notion of transitivity (if a < b and b < < c, then a < c). Thus, if a and b were compared, and b and c were compared, then a might not need to be compared with c.
7. More discussion (can be done later): "Does your starting position make a difference in the end?" NO! The sorting network works no matter how you start.
8. Even more discussion (can be done later): "What if the smaller value goes right and the larger goes left?" Answer: the values will be sorted in decreasing order rather than increasing.



---

9. Hand out the 4-sorter placemats and 4 numbered chips to each pair of students. Let them spend a few minutes pushing the chips through the networks.  Encourage them to voice their observations if they want.
10. Follow this activity with the questions above if you didn't have time to do them before.

---

11. Next challenge the students to make their own sorting network for 3 elements. For younger students you might want to supply the incorrect 3-sorter worksheet and ask them if it always sorts correctly. Give them tokens with numbers on them to push through the network, and see if they always come out sorted regardless of how they are arranged as input. They should be able to discover the error in the network. Ask them to fix the network. Older students will either design a correct network, or else design something like the flawed one, at which point you can remind them that a correct network must work no matter how the values are entered..
12. Advanced students can be challenged to design networks for sorting 4 or more numbers.

---

13. Another fun activity is to divide the class into two or more groups and have each group add up a collection of 4-digit numbers as fast as possible. (Here is a set of numbers to use with this activity.) Encourage the students to think about how they can divide up (parallelize) the work among their group members (multiple "processors") in order to solve the problem efficiently. Give the teams some time to plan their strategies, then let everyone start adding at the same time.

    The best solution should be one that keeps as many students as possible busy for as long as possible. For example, if we had 16 numbers and 8 students, the first step might be to have each student add two numbers. Then in the second step four students can each add together two of the sums from step 1. Then in the third step two students can each add together two of the sums from step 2. (At this point you might want to start thinking about who's the fastest at adding!) Finally, your bestest and brightest math whiz can add together the two totals from step 3.

    In practice, the race may still be won by the students who add the fastest, or by the students who are the most careful about adding correctly. Explain that computers always take the same time to add two numbers, and don't make mistakes. (They are a great equalizer!) The real value of this exercise is in planning the operations so that the sum can be found in the fewest number of steps.

    After discussing the different strategies that the teams used, try having the whole class add different numbers together to show, hopefully, that more people can be used to make the computation faster, and this is an example of why lately, most computers have multiple "cores" (processors).

Conclusion:

Discuss processes from everyday experience that can be accelerated using parallelism. For example, cooking a meal would be a lot slower using only one burner because items would have to be cooked one after the other. Have the kids think of other examples from their lives where parallelism occurs. Can the students think of instances where parallelism doesn't work? Some process are inherently sequential: If you had enough arms, you could probably put your pants and shirt and hat on all at once (in parallel), but no number of arms would let you put your shoes on at the same time you put your socks on.

Evaluation:

Extensions:

The students may be interested in exploring whether or not the network sorts if it is used backwards. It won't, necessarily. See if the students can find an example input which comes out in the wrong order. Use this opportunity to reinforce the notion that something which sometimes works, and sometimes doesn't, isn't much help in solving a problem.

Discuss the fact that the sorting network for a particular number of inputs is not unique. Let the students try to come up with different networks for 4 inputs. Which runs faster? How can you tell?

Design a network to find the minimum or maximum value of the inputs.

It is an exercise in simple combinatorics to find the total number of ways the inputs can be arranged. These arrangements are called permutations, and for n inputs there are n! = n (n-1)...2 of them. (n! is "n factorial") One way to explain this is to note that there are n different ways of selecting the first input value from among the n original items. Then, for each of these n ways, there are (n-1) ways of selecting the second value, for a total of n(n-1) ways of selecting the first two values. For each of these n(n-1) ways, there are (n-2) ways of selecting the third input, for a total of n(n-1)(n-2) ways of selecting the first 3. Continue in this way to see that there are n! total ways of arranging the n inputs.

It is difficult to determine whether or not a given sorting network works for every possible input. The only way to check appears to be to try all possible permutations as inputs, and see if they always come out sorted. Advanced students can be asked how long it would take to check a network with, say, 100 inputs, if we could try a million permutations each second. (The answer is that the sun will have long since burned out.)

A clever variation of the sorting net activity, suggested by Richard Clift, is to run the activity without any sorting net at all! On the playground, or in the classroom, set up instruction cards telling students which location to go to in order to meet up with another student to compare values. At that location, you'll have pre-placed a card explaining where the larger should go from there, and where the smaller should go. At those locations they'll meet another student, compare, and so on. The "net" only exists logically, and not physically. Thus, in this imaginary net, the playground locations play the role of comparison nodes, and the instruction cards at each location replace the paths indicating where to go next. When they all arrive at, say, a row of numbered desks in order, they'll be quite intrigued.

If you'd like to try a bigger sorting net, here's the map of an 8-sorter network.

Standards:

• NCTM K-4:  1, 2, 3, 4, 7, 8, 12, 13.
• NCTM 5-8:  1, 2, 3, 4, 5, 8.
• NCTM 9-12:  1, 2, 3, 4, 12.

Skills:

• Problem solving / reasoning / communication / connections
• Comparison (ordering) of 2 items of any type
• Addition of any type of number
• Understanding parallel processing