For a while now I’ve had my own manual sorting algorithm that I use for, for example, sorting cards.
Actually the thing I most often end up sorting is card sleeves. Our Magic drafting group, being a highly distilled collection of nerds, draft into sleeves that are marked with the pack (A-C) and pick order (1-15), so that we can reconstruct and analyse the draft afterwards. So at some point before every draft I need to un-sleeve the previous draft, then sort the sleeves from A1 to C15.
Now… there’s a whole branch of computer science devoted to sorting algorithms (and by “branch” I mean “volume of the Knuth books”), but I’ve never come across any kind of systematic advice for sorting manually, i.e. without the convenience of having a computer instead of a brain and a bunch of digital artifacts instead of some physical pieces of plastic or cardboard. Most people just tend to sort in an ad-hoc way that vaguely resembles an insertion or selection sort. Occasionally I’ve seen someone attempt a radix sort with playing cards (into numbers, then into suits). If you watch this lecture you’ll see someone try to do a bubble sort with a bag over his head.
My manual sorting algorithm isn’t, as far as I know, a well-known programmatic sorting algorithm. You probably wouldn’t want it to be. It involves a variable number of variable-length lists, and doesn’t perform obviously better than a whole class of O(n2) algorithms that are in-place and much easier to implement. But it has the advantage that, for input that’s approximately O(a deck of cards), its space complexity is roughly O(a small area on my desk).
Here’s the algorithm. It’s in two passes.
- Take a card from the deck. Look for a pile on the table (initially there are none) whose top card is lower than the card you’re holding. Put the card on face-up top of that pile. If there’s no such pile, put the card in a new pile. Repeat until the deck is empty.
- Find the highest card among the top cards of the piles on the table. Move that card to the deck. Repeat until there are no piles left.
That’s a pretty sparse explanation. I might take a shot at making a video with actual cards – not that I expect it to be very useful, but it would also serve the purpose of playing with the 5D Mk II’s video mode.
One interesting thing is that the algorithm sort of takes advantage of the fact that a human can pick one from a handful of cards or piles at a glance in roughly constant time – or, at least, it doesn’t quite feel like a linear search because you quickly pick up ad-hoc shortcuts to find the right pile. (Also, the overhead of physically moving the cards around, which you can’t get away from using any technique, outweights the time it takes you to find the right pile.)
Even if you do end up doing a linear search for the right pile, the time complexity isn’t too bad. Worst case is quadratic, where the cards start in reverse order and each card ends up in its own pile. Best case is linear, where the cards start in order and all the cards go in one pile. The expected complexity for shuffled cards is… I dunno, I haven’t worked it out. The important factor is the average number of piles you end up with, which is complicated. I’d guess it works out to something like √n, which would make the whole thing O(n3/2), maybe. You could look at it as a selection sort with a probabilistic speedup for the “selection” bit.
Anyway, that’s how I’ve been sorting card sleeves for a while. I hope someone found that interesting. And if this is acutally a well-known algorithm, let me know what it’s called. (Haven’t really looked for it myself yet. My Knuth books are at work at the moment, so I might check there on Monday.)No comments