Sorting cards using max 3 stacks

Question

You have a stack of N cards numbered from 1 to N in random order.

You want to sort the cards in ascending order using the following procedure:

1. Your initial stack is stack 1.
2. You distribute the cards from stack 1 to stack 2 and 3: you take the topmost card on stack 1, put it on top of stack 2 or stack 3, and repeat until stack 1 is empty.
3. Then you continue with stack 2: you distribute all cards from stack 2 to the existing stack 3 and a new stack 4, according to the same procedure.
4. Continue with the next stacks: stack $k$ is distributed to stack $k+1$ and stack $k+2$.
5. To end the process, some stack $M-1$ is transferred to the stack $M$, one card at a time.

As you can see, only 3 stacks exist at any time. Therefore the 3 stacks in the title.

The question is: if you use a total of M stacks (initial and final stack included), how many cards can you sort regardless of the initial order?

---

Additional notes:

You choose on which stack to distribute a card. The numbers are visible. You have to figure out the method that maximizes the number N of cards you can sort.

A valid answer should explain why, not just provide the correct maximum.

You start with 1 single stack of N cards in random order.

You must end with all cards sorted, card 1 at the bottom and card N at the top. (It doesn't really matter, but end it the same way regardless of the starting position).

I have a method but I haven't proven it maximal. I'll accept any result at least as good as mine (but I don't tell what it is).

An algorithm isn't requested, only the value of N. But you should provide a convincing proof that your best N is indeed achievable. This almost implies the algorithm is made explicit.

---

There is a solution in O(log(N)) stacks.

With 5 stacks you can sort 5 cards.

Answer 1

With $M$ stacks we can sort $F_M$ numbers

^{(where $F_M$ is the $M$-th Fibonacci Number)}

This is an answer for the call for generalization in OP's answer, by generalizing his/her method.

For comparison with other answers, the asymptotic $N$ as $M$ goes to infinity is $C\varphi^N$ (where $\varphi$ is the golden ratio: $1.61803398875\ldots$) for some constant $C$. Why is this true can be read in the Wikipedia article.

Note that, compared to user3294068's answer, which asymptotically uses $C2^{\frac{N}{2}} = C\sqrt{2}^N$, this algorithm is definitely better for larger $N$ ($\sqrt{2} = 1.41421356\ldots$).

I'll divide this answer to three sections: a visualization of the algorithm, the general idea how it works, - which leads to the final part - and the general procedure for any $M$.

Visualization of Algorithm

This section will explain the algorithm in OP's answer through step-by-step visualization.

For completeness, I'll copy his algorithm here, slightly modified to generalize the algorithm:

The rule is simple to follow: move each card to the next stack, unless the number is forbidden for that stack in which case you put it on the following one. When all the cards are on final stack, the numbers are sorted.

For $M=6$, the forbidden numbers are as follows:

Stack 1: none.

Stack 2: 1,6,7.

Stack 3: 3,4.

Stack 4: 7,8.

Stack 5: 1,2,3.

Stack 6: none.

Due to my limited knowledge of LaTeX, I'll draw the stacks sideways, from bottom to top.

So, initially we have stack 1 ($S_1$) and that it has nothing forbidden ($\{\}$), containing the number $1$ to $8$. We do not know in what order they are initially, so we group them together, like this:

$$ \begin{eqnarray} S_1\{\}&:& \boxed{12345678} \end{eqnarray} $$

The grouping means the number in that group can be in any order.

Next, we have Stack 2 forbidding three numbers ($S_2\{1,6,7\}$), and Stack 3 forbidding two numbers ($S_3\{3,4\}$), like this:

$$ \begin{eqnarray} S_1\{\}&:& \boxed{12345678}\\ S_2\{1,6,7\}&:&\\ S_3\{3,4\}&:& \end{eqnarray} $$

Then we put the numbers from Stack 1 to Stack 2 if it's not forbidden, else put in Stack 3. We'll end up like this (red means it's no longer there):

$$ \begin{eqnarray} S_1\{\}&:& \color{red}{\boxed{12345678}}\\ S_2\{1,6,7\}&:& \boxed{23458}\\ S_3\{3,4\}&:& \boxed{167} \end{eqnarray} $$

Next, we have Stack 4 with its 2 forbidden numbers:

$$ \begin{eqnarray} S_1\{\}&:& \color{red}{\boxed{12345678}}\\ S_2\{1,6,7\}&:& \boxed{23458}\\ S_3\{3,4\}&:& \boxed{167}\\ S_4\{7,8\}&:& \end{eqnarray} $$

Then, after distributing Stack 2 to Stack 3 and 4 we have this:

$$ \begin{eqnarray} S_1\{\}&:& \color{red}{\boxed{12345678}}\\ S_2\{1,6,7\}&:& \color{red}{\boxed{23458}}\\ S_3\{3,4\}&:& \boxed{167}\boxed{258}\\ S_4\{7,8\}&:& \boxed{34} \end{eqnarray} $$

Note that in Stack 3, the group containing $258$ is on top of the group containing $167$, although in each group the order is arbitrary. So at this point Stack 3 might contain $671285$ or $761258$, but not $168257$.

This means, when splitting Stack 3 to Stack 4 and 5, group containing $258$ is split before the group containing $167$, so we have the following:

$$ \begin{eqnarray} S_1\{\}&:& \color{red}{\boxed{12345678}}\\ S_2\{1,6,7\}&:& \color{red}{\boxed{23458}}\\ S_3\{3,4\}&:& \boxed{167}\color{red}{\boxed{258}}\\ S_4\{7,8\}&:& \boxed{34}\boxed{25}\\ S_5\{1,2,3\}&:& \boxed{8} \end{eqnarray} $$

$$ \begin{eqnarray} S_1\{\}&:& \color{red}{\boxed{12345678}}\\ S_2\{1,6,7\}&:& \color{red}{\boxed{23458}}\\ S_3\{3,4\}&:& \color{red}{\boxed{167}\boxed{258}}\\ S_4\{7,8\}&:& \boxed{34}\boxed{25}\boxed{16}\\ S_5\{1,2,3\}&:& \boxed{8}\boxed{7} \end{eqnarray} $$

Note that at Stack 5, each group contains only one element, this means there is no variation, and so at this point, we can be sure that Stack 5 contains $8$ at the bottom and $7$ on top of it. Continuing this, we have:

$$ \begin{eqnarray} S_1\{\}&:& \color{red}{\boxed{12345678}}\\ S_2\{1,6,7\}&:& \color{red}{\boxed{23458}}\\ S_3\{3,4\}&:& \color{red}{\boxed{167}\boxed{258}}\\ S_4\{7,8\}&:& \color{red}{\boxed{34}\boxed{25}\boxed{16}}\\ S_5\{1,2,3\}&:& \boxed{8}\boxed{7}\boxed{6}\boxed{5}\boxed{4}\\ S_6\{\}&:& \boxed{1}\boxed{2}\boxed{3} \end{eqnarray} $$

And finally moving the whole Stack 5 into Stack 6 will give us sorted from $1$ at the bottom to $8$ at the top.

Insights

So, observing the process above, we see that the algorithm works by splitting the numbers into multiple groups, each containing less elements than before, ensuring that when the group size finally reach 1, they are all in order.

Therefore, to generalize this, we need to find how to split the numbers into groups of smaller size.

First, note that the restriction to use only 3 groups means if we have $k$ group in Stack $i$, we can split them into $k$ groups in Stack $i$ and $k$ group in Stack $i+1$. This implies the number of groups in Stack $i$, which comes from Stack $i-2$ and Stack $i-1$, is at most the sum of number of groups in Stack $i-2$ and Stack $i-1$. Formally, if $G_i$ denotes the number of groups in Stack $i$, we have:

$$ G_i = G_{i-1} + G_{i-2} $$

Initially we have only one group in Stack 1, and later we can have at most 1 group in Stack 2. This gives $G_1 = G_2 = 1$, which makes $G_i = F_i$, where $F_i$ is the $i$-th Fibonacci number. So with $M$ stacks, we can sort $F_M$ numbers (precise answer).

Next, we can use the similar reasoning to prove the optimality of this algorithm. Note that at the end we must have $N$ groups, each containing one number. So considering the first insight above, the maximum number of groups at Stack $M$ is $F_M$, therefore we can't have less than $M$ stacks to sort $F_M+1$ numbers. So, by taking $M$ such that $F_{M-1} < N \leq F_M$ (which would be about $\lfloor \log_\varphi \left(N\sqrt{5}+\frac{1}{2}\right)\rfloor$ according to the Wikipedia article), it is the minimum required (and sufficient) to sort $N$ numbers.

Generalization Procedure

Now we come to the interesting part, how can we generalize this to any $M$, not just $M=6$ like in the example? More specifically, how should we assign the set of forbidden numbers for each Stack?

For this, we can work backward from Stack $M$ down to Stack 1, assuming maximum possible $N$. Note that the set of forbidden numbers for $M$ stacks will work for any $N$ less than the maximum $N$ (the numbers is guaranteed to be sorted at Stack $M$).

First, we know that there are $F_M = N$ groups at Stack $M$ at the end. One step before (that is, after we emptied Stack $M-2$), there are $F_{M-1}$ groups in Stack $M-1$ and $F_{M-2}$ groups in Stack $M$.

Next, we know that in order for those first $F_{M-2}$ numbers to be in Stack $M$, they must be forbidden at Stack $M-1$ (because those numbers come only from Stack $M-2$, so those numbers can't ever be inside Stack $M-1$). So we now know the forbidden numbers at Stack $M-1$.

To continue, we note that in the algorithm, we split groups, so now we need the reverse, which is to merge groups. We know that the $i$-th top-most group in Stack $M-1$ would have come from the same group in Stack $M-2$ as the $i$-th top-most group in Stack $M$. This enables us to reverse the process, and continue numbering the forbidden numbers in the same way until we get back to Stack 1.

For example, here is the procedure for $M=7, N=13$:

$$ \begin{eqnarray} S_7\{\}&:& \boxed{1}\boxed{2}\boxed{3}\boxed{4}\boxed{5}\boxed{6}\boxed{7}\boxed{8}\boxed{9}\boxed{10}\boxed{11}\boxed{12}\boxed{13} \end{eqnarray} $$

---

$$ \begin{eqnarray} S_6\{1,2,3,4,5\}&:&\boxed{13}\boxed{12}\boxed{11}\boxed{10}\boxed{9}\boxed{8}\boxed{7}\boxed{6}\\ S_7\{\}&:& \boxed{1}\boxed{2}\boxed{3}\boxed{4}\boxed{5}\color{red}{\boxed{6}\boxed{7}\boxed{8}\boxed{9}\boxed{10}\boxed{11}\boxed{12}\boxed{13}} \end{eqnarray} $$

---

$$ \begin{eqnarray} S_5\{11,12,13\}&:&\boxed{56}\boxed{47}\boxed{38}\boxed{29}\boxed{1\ 10}\\ S_6\{1,2,3,4,5\}&:&\boxed{13}\boxed{12}\boxed{11}\color{red}{\boxed{10}\boxed{9}\boxed{8}\boxed{7}\boxed{6}}\\ S_7\{\}&:& \color{red}{\boxed{1}\boxed{2}\boxed{3}\boxed{4}\boxed{5}\boxed{6}\boxed{7}\boxed{8}\boxed{9}\boxed{10}\boxed{11}\boxed{12}\boxed{13}} \end{eqnarray} $$

---

$$ \begin{eqnarray} S_4\{4,5,6,7\}&:&\boxed{1\ 10\ 11}\boxed{2\ 9\ 12}\boxed{3\ 8\ 13}\\ S_5\{11,12,13\}&:&\boxed{56}\boxed{47}\color{red}{\boxed{38}\boxed{29}\boxed{1\ 10}}\\ S_6\{1,2,3,4,5\}&:&\color{red}{\boxed{13}\boxed{12}\boxed{11}\boxed{10}\boxed{9}\boxed{8}\boxed{7}\boxed{6}}\\ S_7\{\}&:& \color{red}{\boxed{1}\boxed{2}\boxed{3}\boxed{4}\boxed{5}\boxed{6}\boxed{7}\boxed{8}\boxed{9}\boxed{10}\boxed{11}\boxed{12}\boxed{13}} \end{eqnarray} $$

---

$$ \begin{eqnarray} S_3\{1,10,11\}&:&\boxed{3\ 4\ 7\ 8\ 13}\boxed{2\ 5\ 6\ 9\ 12}\\ S_4\{4,5,6,7\}&:&\boxed{1\ 10\ 11}\color{red}{\boxed{2\ 9\ 12}\boxed{3\ 8\ 13}}\\ S_5\{11,12,13\}&:&\color{red}{\boxed{56}\boxed{47}\boxed{38}\boxed{29}\boxed{1\ 10}}\\ S_6\{1,2,3,4,5\}&:&\color{red}{\boxed{13}\boxed{12}\boxed{11}\boxed{10}\boxed{9}\boxed{8}\boxed{7}\boxed{6}}\\ S_7\{\}&:& \color{red}{\boxed{1}\boxed{2}\boxed{3}\boxed{4}\boxed{5}\boxed{6}\boxed{7}\boxed{8}\boxed{9}\boxed{10}\boxed{11}\boxed{12}\boxed{13}} \end{eqnarray} $$

---

$$ \begin{eqnarray} S_2\{3,4,7,8,13\}&:&\boxed{1\ 2\ 5\ 6\ 9\ 10\ 11\ 12}\\ S_3\{1,10,11\}&:&\boxed{3\ 4\ 7\ 8\ 13}\color{red}{\boxed{2\ 5\ 6\ 9\ 12}}\\ S_4\{4,5,6,7\}&:&\color{red}{\boxed{1\ 10\ 11}\boxed{2\ 9\ 12}\boxed{3\ 8\ 13}}\\ S_5\{11,12,13\}&:&\color{red}{\boxed{56}\boxed{47}\boxed{38}\boxed{29}\boxed{1\ 10}}\\ S_6\{1,2,3,4,5\}&:&\color{red}{\boxed{13}\boxed{12}\boxed{11}\boxed{10}\boxed{9}\boxed{8}\boxed{7}\boxed{6}}\\ S_7\{\}&:& \color{red}{\boxed{1}\boxed{2}\boxed{3}\boxed{4}\boxed{5}\boxed{6}\boxed{7}\boxed{8}\boxed{9}\boxed{10}\boxed{11}\boxed{12}\boxed{13}} \end{eqnarray} $$

---

$$ \begin{eqnarray} S_1\{\}&:&\boxed{1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ 10\ 11\ 12\ 13}\\ S_2\{3,4,7,8,13\}&:&\color{red}{\boxed{1\ 2\ 5\ 6\ 9\ 10\ 11\ 12}}\\ S_3\{1,10,11\}&:&\color{red}{\boxed{3\ 4\ 7\ 8\ 13}\boxed{2\ 5\ 6\ 9\ 12}}\\ S_4\{4,5,6,7\}&:&\color{red}{\boxed{1\ 10\ 11}\boxed{2\ 9\ 12}\boxed{3\ 8\ 13}}\\ S_5\{11,12,13\}&:&\color{red}{\boxed{56}\boxed{47}\boxed{38}\boxed{29}\boxed{1\ 10}}\\ S_6\{1,2,3,4,5\}&:&\color{red}{\boxed{13}\boxed{12}\boxed{11}\boxed{10}\boxed{9}\boxed{8}\boxed{7}\boxed{6}}\\ S_7\{\}&:& \color{red}{\boxed{1}\boxed{2}\boxed{3}\boxed{4}\boxed{5}\boxed{6}\boxed{7}\boxed{8}\boxed{9}\boxed{10}\boxed{11}\boxed{12}\boxed{13}} \end{eqnarray} $$

Bonus: Generalization of the problem

Now, the above solves the problem of finding maximum $N$ given $M$ stacks, clearing one stack at a time, and using only 3 stacks at a time. What if we remove that last restriction? How many numbers can we sort? (Ok, I admit that I've been nerd-sniped)

Note that if we can use 4 stacks, then we can split a Stack into 3 stacks, and so the number of groups in a stack depends on the previous 3 stacks, giving us Tribonacci Number with $F_{(3)}(1) = F_{(3)}(2) = 1$, for which the asymptotic ratio is about $1.83929$.

For fun, here is the final diagram when we can use 4 stacks ($M=5, N=F_{(3)}(5)=7$):

$$ \begin{eqnarray} S_1\{\}&:& \color{red}{\boxed{1234567}}\\ S_2\{3,4,7\}&:& \color{red}{\boxed{1256}}\\ S_3\{1,6,7\}&:& \color{red}{\boxed{34}\boxed{25}}\\ S_4\{1,2,3\}&:& \color{red}{\boxed{7}\boxed{6}\boxed{5}\boxed{4}}\\ S_5\{\}&:& \boxed{1}\boxed{2}\boxed{3}\boxed{4}\boxed{5}\boxed{6}\boxed{7} \end{eqnarray} $$

The more stacks we can use, the higher the asymptotic ratio is. You can check Tetranacci Number, Pentanacci Number, and so on in this very helpful Wikipedia article, which states that the limit of the ratio is $2$. So asymptotically, we can sort $C\cdot2^M$ numbers with $M$ stacks (actually the exact number is $2^{M-2}$ if we are allowed to use all available stacks).

---

With this, finally I can tell OP, that the problem is solved. (reference to this comment)

_{Ok, you might notice that I'm heavily influenced by What-If XKCD style. That's my favorite reading!}

Answer 2

Update:

Thanks to hints in the comments, I realized there is a 33% more efficient solution. It is possible to sort up to $N = 2^i$ cards using $M = 2i+1$ stacks. My algorithm is: split, flip, merge, repeat. If you perform the split differently, you don't need the flip step. You just split, merge, repeat. This algorithm must be optimal, as with a single split/merge you can only sort one bit of information.

Split algorithm: For each card numbered $i$, count the bits of $i-1$. If there are an even number of bits, put the card on stack 2, odd number on stack 3. In the second pass, ignore the lowest bit. Third pass ignore the first and second bits, etc. So, first pass card 1 goes on stack 2, 2 -> 3, 3 -> 3, 4 -> 2, 5 -> 3, 6 ->2, 7 -> 2, 8 -> 3, etc.

After each split, merge the stacks by putting each card from stack 2 onto stack 3, etc.

Original answer:
Here is a plan that should work:

1. Move all the odd cards to stack 3 and all the even cards to stack 2.
2. Move all the cards from stack 2 to stack 1.
3. Move all the cards from stack 3 to stack 1.

If you have up to 2 cards, you are now finished.

4. Move all the cards equal to 1,2 mod 4 to stack 3 and the others to stack 2.
5. Move all the cards from stack 2 to stack 1.
6. Move all the cards from stack 3 to stack 1.

If you have up to 4 cards, you are now finished.

7. Move all the cards equal to 1,2,3,4 mod 8 to stack 3 and others to stack 2.
8. Move all the cards from stack 2 to stack 1.
9. Move all the cards from stack 3 to stack 1.

If you have up to 8 cards, you are now finished.

Continue following the pattern. The total number of steps required is $3 \log_2 N$, rounding up to the next multiple of 3.

This works because each set of 3 steps sorts cards based on the lowest unsorted bit, and no steps later mess up that ordering. In other words, after step 3, card 1 is guaranteed to be above card 2, card 3 above card 4, etc. Later sets of steps will preserve that ordering while fixing ordering of groups.

To help visualize, a walkthrough with 4 cards:

No matter the initial ordering, after step 1, stack 2 has cards 2 & card 4 in some order, while stack 3 has cards 1 & 3 in some order. After step 3, stack 1 has (1, 3), (2,4) where the two groups are in random order. After step 4, stack 2 has cards 4 & 3 (4 on top) and stack 3 has cards 2 & 1 (2 on top). After step 6, stack 1 has cards 1, 2, 3, 4, in that order from the top.

Update: Rereading the question, I see an algorithm wasn't requested. The answer is: given $M$ stacks, you can sort up to $2^i$ cards, where $M = 3i+1$.

I think my approach is optimal. I know you need $O(\log_2 N)$ stacks to sort $N$ cards.

Answer 3

Let me start off with a very weak strategy. I'm sure there are better strategies but at least there is an answer.

Step 1:
move cards to stack 3 until you encounter card 1 and put that in stack 2. keep repeating this for every next card in order until stack 1 is empty.

you now have:
stack 2: cards 1 till x in ascending order
stack 3: cards x+1 till N in random order

Step 2:
move all cards in stack 2 to stack 4

you now have:
stack 3: cards x+1 till N in random order
stack 4: cards 1 till x in descending order

Step 3:
move all cards in stack 3 to stack 5

you now have:
stack 4: cards 1 till x in descending order
stack 5: cards x+1 till N in random order

Step 4:
move all cards in stack 4 to stack 6

you now have:
stack 5: cards x+1 till N in random order
stack 6: cards 1 till x in ascending order

Now repeat these 4 steps. this means: put cards in stack 7 until you find card x+1 and put that in stack 6. and keep doing that in a way so you have stack 6 in ascending order. and so on.

Worst case scenario: every 4 steps only 1 card gets added to the "in order" stack. With this strategy you have with N=1 that M=2 and N=2 that M=6 In other words: with M stacks you can only order (M+2)/4 cards rounded down if I'm not mistaken.

Answer 4

So far nobody has given an optimal answer.

Here is what I believe is the optimal answer for 6 stacks. It can sort 8 numbers.

The rule is simple to follow: move each card to the next stack, unless the number is forbidden for that stack in which case you put it on the following one. When all the cards are on stack 6, the numbers are sorted.

The forbidden numbers are as follows:
Stack 1: none.
Stack 2: 1,6,7.
Stack 3: 3,4.
Stack 4: 7,8.
Stack 5: 1,2,3.
Stack 6: none.

Following this, from stack 1, cards 2,3,4,5,8 go to stack 2, cards 1,6,7 go to stack 3. Then, from stack 2, cards 2,5,8 add to stack 3, cards 3,4 go to stack 4. etc. You can try, it works!

Is there anyone who can generalize this to M stacks?

Answer 5

Given stacks M, I believe you can sort up to 2^i records, where m = 2*i + 1. Effectively, you can do a binary sort, but since you include a starting column, you require 1 extra. I'll try to get an algorithm up later.

Edit: After trying to put my idea into words and looking at @user3294068's answer, I think i have the same solution (with a slightly different sort algorithm), but it ends up with the same number of columns.