Efficient ways to sort a deck of actual cards

Question

I often have to sort decks of cards. These are "collector" cards numbered from 1 to 216 and there are doubles and missing numbers.

I'm looking for sorting algorithms that work well with physical cards. Insertion sort seems fine because inserting a card does not require a shift of the subsequent cards like in a computer memory. However, scanning through a large deck is time consuming. With a large deck, there are even chances that you might drop the deck and have to restart the sort.

I could draw the cards on a large table and directly place each card to its correct location but this takes quite a lot of space and is not very convenient.

My usual approach is to do a first scan through the deck and put them in stacks 1-49, 50-99, 100-149, 150-199, 200+. Then I scan each deck and put them in stacks 0, 1, 2, 3, 4. And finally, I apply an insertion sort on each 10-pack. This remains a tedious process though.

Another idea is to take the 50 stacks and sort them roughly. 25 would go around the middle, 40 somewhere near the end of the stack and so on. That quickly brings a roughly sorted 50-deck and I can easily scan through it and fix the sorting.

I was wondering whether a more sophisticated algorithm could be applied conveniently to a physical deck. I don't see how we could apply quick sort and thing like heap sort require to know the index of the card within the deck.

Answer 1

I think counting sort together with your insertion sort approach could work well: scan for the ones and put them first, then the twos and so on.

This might look like a lot of work since your cards are numbered from 1 to over 200, but I think in this case everything will be a lot of work. You can speed things up by doing multiple cards at once, which shouldn't be too hard: scan for the ones, twos and threes (and more if you're up for it) all at once, and put them in corresponding positions (combining with "insertion sort" so you don't have to leave an empty space between cards).

Answer 2

I think that a kind of quick sort is the easiest way for this. I think there were even some Youtube videos showing people doing this with a normal poker deck.

You go through the deck and put all cards smaller than 100 on a left pile, all bigger on a right pile. Then you recurse through the piles, depth first (so you do not have too many piles at once). At some threshold (perhaps about 5 cards), you simply sort "in hand" (similar to insertion sort, perhaps). Finally, you stack the piles together.

You could also do a merge sort: Divide the pile into two, recurse depth first, until you arrive at two piles of 5 cards each. Sort these two piles "in hand", then put them face up side by side. Merge them into a result pile by always putting the lower of the showing cards on the result pile. You can see which piles are already sorted by leaving those face up. Make sure to always merge piles of similar size, otherwise proceed to split up the next unsorted pile.

Edit: radix sort could be good, too: Put the cards into ten piles by their last digit, stack these piles together in order. Then, put the cards into ten piles by their second-to-last digit, stack them together in order again. Finally, put them into piles by their third-to-last digit (according to your discription, that is the first digit), and stack these together, done. This might be the easiest, after all, and it is O(n) (you need three passes through the deck).

Answer 3

The reason I ask about actual total numbers and sizes is that if the total area of all possible cards is sufficiently small, it may well be possible to just: go through the deck laying them all out into a grid, each card going in its correct spot, and then simply pick them up in order.

For example, were there a maximum of 100 cards, numbered 1-100, imagine that your working surface is divided into a 10 x 10 rectangular grid; then as each card is processed, put eg card 67 in the 7th column of the 6th row. Once all the cards are laid out, pick them up in order.

This only works if your working surface is large enough to contain all the cards, but if they are normal playing card size and you have a nice big table, it should be able to cope with the 200 you mention, especially as you can easily overlap the 'cells' and have the method still work.

For me this is the approach which makes most use of the fact that this is a problem in physical space, rather than in bits - each physical object is processed only twice (once to put it in place, once to pick it up), because for an algorithm involving physical objects, moving them around has much greater cost than thinking about what to do.

Answer 4

I have taught university classes that are sometimes on the large side, and I have had practice with the similar task of sorting graded exams. I almost always use bucket sort, like you do. You also mention a merge sort approach, which I also sometimes do, but it only saves time when you start with sorted subpiles, not with a totally scrambled set of cards.

There are tricks to speed up the bucket sort. Much of the time in a human bucket sort is spent calculating the bucket for the next item. You can try two tricks. First, you can bucket sort by digit, which I guess is called radix sort, so that you never have to compare numbers. The first stage uses three buckets, which is not very many but could be okay. The second stage is the "main" work, with ten buckets. In the third stage, you are sorting ten numbered cards and common sense suggests insertion sort. But even for that stage, a radix sort could speed things up, even though each bucket only gets one card. Of course, you shouldn't use "buckets" with four sides, but just piles of cards on a table. You would only use the bucket method for the units digit if it is easy to sweep up the cards in order. Possibly for the middle stage, a slot with three sides would work better than an open pile of cards.

A second trick is to label the locations on the table 0 through 9 so that you can find the right pile more quickly. The labels can be taped onto the table so that you can reuse them.

I'm not sure if this particular bucket sort strategy is the best one. The point is that bucket sort is the most common method for sorting midterms, and probably best for large decks of cards too. There are several variations to try and you should experiment a little to see which one works best.