Ideal amount of piles to sort a stack of 250 cards (magic the gathering)

Question

I'm a hobbyist working on a mechanical sorting machine to sort magic the gathering cards. I'm by no means a mathematician though, and I was wondering if you all wouldn't mind helping me out with a math puzzle to determine the best route to go with my machine.

The average Magic: the Gathering set of cards contains 250 unique cards. My machine will sort those cards alphabetically placing the cards into multiple piles repeatedly to filter the cards down into the correct position. My question is, how many piles would be needed to sort 250 cards with only three passes. Here is some further info more clarification of the question.

Example: a card passes through the scanner, and the computer determines that the cards position in the alphabetized set is within the first 50 positions of the alphabetized set. 50 positions is %20 percent of a 250 card set, which I've chosen that number. It just seems like an easy place to start.

Then the next card passes through, and the scanner determines that the cards position is in the 3rd 50 positions of the alphabetized set (positions 101-150) so it places this in pile three. It keeps doing this until it has 250 cards broken down into 5 piles.

The cards are then scanned again for further refinement until they are in the correct order. So the question is, how many piles would make it possible to on average sort a 250 card set in 3 passes. I only chose 5 piles to illustrate the question, so I hope that's not confusing.

What is the most optimal number of piles needed?

Answer 1

In the abstract, it seems you have $250$ cards, each one identified by its rank in some kind of canonical sorting. Presumably, you have mechanical limitations, because otherwise, your best bet would be to simply sort in one pass, using a trivial hash sort that just puts them in the right order. This essentially creates $250$ piles. Since you're not doing that, I'm assuming that $250$ piles is not a practical solution.

If you want to sort in three passes, one way to do that is to represent each card by its rank as a three-digit, base $7$ number. We choose $7$ because $7^3 = 343 > 250$. Thus, for instance, the $192$nd card is $363$ in base $7$, because $3\cdot 7^2+6\cdot 7+3 = 147+42+3 = 192$. Some cards with lower-numbered ranks will have leading zeros in this representation—for instance, card number $4$ is $004$, and card number $19$ is $025$.

Then, in the first pass, you sort each card by its last digit, placing each card whose last digit is $0$ in the first pile, whose last digit is $1$ in the second pile, and so on. Collect all the piles, at the end of the first pass, keeping each pile internally intact, and you have a deck which is sorted in order of last digit.

In the second pass, you sort each card by its middle digit, placing each card whose middle digit is $0$ in the first pile, whose middle digit is $1$ in the second pile, and so on. Collect all the piles at the end of this second pass, and you have a deck which is sorted first in order of middle digit, and then in order of last digit.

In the last pass, you repeat the procedure with the first digit. Collect all the piles at the end of this last pass, and you have a deck which is sorted in the proper lexical order.

If you're doing this mechanically, you will also want to make sure that the order is preserved and not reversed, as often happens when cards are placed on top of one another. For example, in the second pass, as you're collecting all the cards whose middle digit is $0$ in the first pile, make sure that the cards are placed so that those that end $00$ are still in front of those that end $01$, which in turn should be in front of those that end $02$, and so forth. Depending on the mechanics of the device, this could be accomplished by turning each card upside-down before placing it in the proper pile.

This is essentially a merge sort. The reason we do this in reverse order of digits is that the last pass provides the high-order digit. Since the high-order digit is lexically first, we run the passes in reverse order.

Answer 2

Well unless you're using exclusively cards from way back in ye oldene dayse (tm), there's a collector number on the card itself, so they're technically already sorted.

Before I begin, let me say: Alphabetically is the absolute WORST way to sort M:tG cards. I personally sort by more effective category: white blue black red green multicolored and colorless (this is referred to as WUBRG order). Some people prefer to place colorless in front due to its ability to fit in any deck, but I feel basic lands go in the back, and the rest of colorless follows suit. After organizing by color it's more helpful to sort the rest of the cards by their converted mana cost, with mana symbols weighted more than numericals.

My preferred method of sorting involves tossing cards into piles based on their color or color combinations or lack of color, then one by one, taking each of those piles and hand-sorting them such that the pile is sorted by CMC. (converted mana cost) If those piles are too large, I may choose to sort by card type as well, which would be creature, planeswalker, instant, sorcery, enchantment, and possibly artifact (rare circumstances, those).

I hope this helps you out better than sorting alphabetically! It does technically use two to three passes.

Best of luck to you while playing, and may the mana screw never find you.