CS Unplugged is the source of many of my activities and demonstrations for introducing concepts in computer science. I recently found that Tim Bell (University of Canterbury, New Zealand) delivered a Google Tech Talk [50 min.] about the project. Here is a much shorter video [1:44] just on the sorting network activity. Watching the kids put themselves in order is pretty amazing, once you get past the silly-looking school uniforms.
Earlier this week, I had an array of students model the gnome sort at the front of the classroom. It really is the simplest sorting algorithm. They stood in some arbitrary order, then I handed the left-most person a page with these instructions:
If there is no one to your right, pass these instructions to the person on your left.
If the person to your right is shorter than you, pass these instructions to the person on your left.
Otherwise, swap positions with the person on your right (but keep the instructions).
Go back to step 1.
They tried it out, and before long they were standing in order by height. (The algorithm is written without a stop condition, so I had to be in the right place as a sentinel.) The follow-up questions: how long did this take? How fast does it go if you're already in the intended order? What if you're in the reverse order? This one is simple to understand because there's only one pointer, and all swaps are local.
