The three-card problem may will allow one to enumerate all possibilities, but using three piles one may in fact solve the problem for an arbitrary number of cards; enumeration of all states will not be possible, but one may formulate invariants which, once established, can be maintained while the cards go through a "loop" of visible states. If one of the invariants is that a certain range of cards is sorted, and a certain through the loop is guaranteed to add at least one card through the range, then repeating the loop will eventually yield a sorted sequence. All that will be left is to define what should happen for visible states that do not appear in the loop, and show that the loop invariants will establish themselves.
For illustrative purposes, I will assume there are thirteen cards, ace through king, and the goal is to have all thirteen on the pile A, ace on top, king on the bottom, and other cards in sequence. The algorithm may be easily adapted to any other number three or greater (sorting two cards with three piles is trivial).
The key invariant is that the king will either be the only card on pile B or C, or else will be the bottom card on pile A, covered by zero or more other cards in direct numerical sequence (i.e. K-Q-J-T-9-8-etc.). If the invariant does not hold, the king may "pop up" unexpectedly and disrupt a step in the algorithm, but once that occurs the king will be visible. When the king is visible, the algorithm will have enough information to clear a spot for it and move what is expected to be a lone king to the empty pile. If the invariant still didn't hold, a cards may unexpectedly "pop up" beneath the king; that could disrupt the algorithm a second time, but moving the king to an empty pile will have established the invariant.
In describing the algorithm, most steps to say that when certain conditions apply, one should repeat an action until a condition occurs. Once the "king invariant" is established and the conditions for an action are established, making the indicated moves will not affect the stated conditions until the pile is vacant, so no memory will be required to continue the action.
- Any time a king is visible in column C, move cards from B to A until B is vacant, then move the king there.
- Any time a king is visible in column B, move cards from A to C until A is vacant, then move the king there.
- Any time C shows a non-king, B doesn't show a king, and A is non-empty, move a card from C. If it's one less than the card on A, move it there; otherwise move it to B. Keep doing until C is exhausted.
- If B doesn't show a king, C is empty, and A is non-king, move A to B until king appears, then move it to C.
- If A is empty and no king is visible, move cards B to C until a king appears or B is exhausted; if A is exhausted, move a card from C to A. This step will not be necessary once the invariant is established, but it might be necessary prior to that.
Note that if B and c are empty and A shows an ace, then the deck is "probably" sorted. This condition may arise once, within the first ten moves, if the deck is not sorted, but every appearance after the first, or after the tenth move, will represent a sorted deck. If one could request, on the first move only, that if column B is empty a card should be moved there, one could avoid any false reports of sorted sequence.
At the end of step 1, assume the bottom of deck A has k cards in order [k may be zero], starting with the queen on the bottom. Then at the end of step 2, those cards will be on the top of C in reverse order. At the start of step 3, those cards will get moved to pile A. Once that is done, pile C will still contain the next card for pile A. Thus, at the end of step 3, pile A will contain at least k+1 correctly-sorted cards in addition to the king. Step 4 will place the correctly-sorted cards in reverse order on the top of pile B, and step 1 will move them to the bottom of deck A. The net effect will be that after the loop has run, if there were k sorted cards, there will now be at least k+1 (except in the case where all the cards were sorted).
With thirteen cards, the maximum number of moves required to establish the invariant will be 33 (assuming e.g. Q/AK/JT98765432). The ten cards from the right pile will be moved to pile A (yielding QJT98765432/AK/-), all eleven cards from the left pile will be moved to the middle (yielding -/23456789TJQAK/-), and twelve cards will be moved from the middle pile to the right pile.
With the invariant established, each pass through the "loop" will take 3n+k moves, where k is the number of cards that are sorted after the pass, and it is possible that only one card will get sorted per pass. The net result is an O(N^2) sort. Still, not too shabby for an algorithm using O(0) space!