Monthly Archives: October 2011

Sorting Networks Activity

Sorting Network in action

A 9-input sorting network in action

Computer Science Unplugged is a wonderful initiative that collects activities that communicate some basic ideas of computer science – without using computers.

IT University of Copenhagen opened its doors to the public last Friday in connection with the city-wide “Culture Night”, so I used the opportunity to implement the Sorting Networks activity.

ITU has a big stair case in its atrium, which had the proper size for a 9-input sorting network. I measured everything up, found a good-looking network in Knuth’s The Art of Computer Programming, and sketched the layout for the friendly folks at Facilities Management.

The network was “drawn” on the stairs using adhesive tape, which took a few hours on the day before the event. It looked absolutely splendid. The activity was manned with enthusiastic undergraduate students for several hours, who herded eager and intrigued guests of all ages through the maze of comparators. A smashing success.

Also, a student volunteered to translate the Wikipedia page on sorting networks into Danish, so the outreach activity had a permanent, digital result as well: Sorteringsnetværk.

Originally, I had also promised myself to produce a large poster or two next to the activity, which should explain what’s actually going on, why sorting is important, and (in particular) show a few more concrete networks of various sizes. This would have given the whole activity a bit more scientific muscle. Alas, I failed to get this done in time. Better next time.

I also failed to show up in time for the kick-off, instructing the student volunteers in how the whole thing was supposed to work. Apparently, they spent a good number of attempts running the network in the reverse direction (from the top of the stairs and down, which arguably is the obvious direction), and tried to find the bug! So now they know that sorting networks don’t necessarily work in both directions. (But insertion sort does!) This may be a fresh research question: find an optimal bidirectional sorting network for 9 inputs.

All in all, a splendid event. Thanks to everybody who helped, or just wanted to get themselves sorted out.