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 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).