Part of my duties for the department involves TAing for a large undergraduate course. At our last meeting we had a discussion about sorting papers. It turns out I have strong opinions on the matter.

The main motivation for sorting papers is that returning papers to students works best if the papers are returned in alphabetical order. If the papers are in order you can make several piles such as A-H, I-P, and Q-Z. This mitigates the feeding frenzy that occurs when you let students pick up their papers. In theory it also lets students find their paper using binary search, but I rarely see this actually happen in practice.

The discussion we had at our meeting was about the optimal way to sort. It apparently has been taking a long time. This doesn't surprise me; I've done a lot of sorting in my time and I've found that the choice of algorithm has a great impact on how long the task takes. Through a good amount of trial and error I've come to find that the best algorithm is radix sort. I'll now share my wisdom.

Radix Sort

Radix sort is a comparison-free divide-and-conquer algorithm for sorting. The implementation is very simple.

Take your stack of papers and find enough space to make 26 piles. Each pile is associated with a single letter. Take a paper off the stack, look at the first letter of the last name, and place the paper in the corresponding pile. Repeat until all papers have been placed in a pile. Now pick up a pile and sort it. If the pile is small enough you can sort intuitively, otherwise carry out another round of radix sort, this time using the second letter of the last name. Do this for every pile. Now pick up the piles in order and everything is sorted.

Advantages

Semi-anytime

An anytime algorithm is one that will always return a valid solution even if its interrupted. I say the radix sort is semi-anytime because after the first step the papers are roughly in order. All of the subsequent steps merely refine that order. This property is nice if you run out of time before class or you don't particularly care that the papers are exactly in order.

This is not the case for other algorithms such as insert sort where if you're interrupted you'll have a sorted pile and an unsorted pile. The students with papers are in the unsorted pile will be angry.

Minimizes comparison

I find it hard to remember the order of the alphabet. Typically I have to resort to (mentally) singing the nursery rhyme to keep it straight. Most methods suffer from delays while you figure out whether "j" is before or after "q"? For radix sort I make post-its to label the piles so I don't have to remember anything.

Parallelizable

The entire process can be done in parallel which can greatly speed up the grading process if you have multiple workers. Workers are also free to leave at anytime without disturbing the process. I haven't been able to try this out, but this seems like it could be a fun project for small children.

Psychologically gratifying

Each pile sorted gives a sense of achievement. This is important to maintain morale. I also find tackling piles in decreasing size enhances this effect as the task becomes progressively easier.

Disadvantages

Space requirements

You need enough space to make your piles. Thus, radix sort doesn't work well in small offices, seminars, or airplanes.

You can mitigate this problem by using fewer piles but this requires more thought about the alphabet and requires more rounds of sorting.

Name distributions aren't optimal

Radix sort works best when the piles are roughly the same size. Unfortunately, the distribution of the letters in last names is not uniform. This results in a few piles being rather large (M and S) while some are small or even empty (U and X).

For when I have tenure

For fun I'd like to implement spaghetti sort. On the first day of class I would give every student a rod whose length corresponds to their alphabetical order. When submitting assignments they would fasten their work to their rod and hand in the rod. Then sorting is as simple as laying out the rods and pulling out the longest rod in order. Bonus points if you can tell me how I could account for dropping/adding students.