Let's switch to zero-based indexing: $$$0, 1, 2, ..., n-1$$$, and for convenience let $$$N = n-1$$$. Notice that this operation sends $$$0$$$ and $$$N$$$ back to themselves, so let's ignore them and focus on indices $$$1...N$$$ for now.

Now, we can represent the swap as moving index $$$x$$$ to $$$f(x)$$$:

You can convince yourself this works: for the first half, $$$x$$$ maps to $$$2x$$$ directly, while for the upper half, it is correct to doubling it, reduce mod $$$n$$$, and add 1 (which is just mod by $$$N$$$).

Then the answer is just the order $$$k$$$, which is the smallest $$$k$$$ s.t.:

You can convince yourself this condition is both necessary and sufficient. Necessary, because for $$$o \lt k$$$, the chip at index $$$1$$$ is routed to $$$2^o$$$ which is not $$$1$$$, and sufficient because with $$$k$$$ operations, every index $$$i$$$ gets mapped back to index $$$i$$$.

Actually finding $$$k$$$ is the discrete logarithm problem; it's famously hard and used in Diffie-Hellman key exchange. For our purposes, we can brute force in $$$O(N)$$$ (we only need to search $$$k = 1...N-1$$$ because remainders $$$\bmod N$$$ cycle every $$$\phi(N)$$$). There are also some algorithms like baby step giant step or Pollard rho that run in $$$O(\sqrt{N})$$$. Nobody knows an algorithm that runs in polynomial of $$$\log N$$$ (number of bits in $$$N$$$, since cryptography-sized $$$N$$$ is usually on the order of $$$2^{2048}$$$) yet.

It turns out is impossible to have white at the bottom and green at the top, unless the stack is also sorted.

First, let's note that the stack is symmetric. If we reversed it, then everything is still the same. So if $$$m \gt \frac{n}{2}$$$, then let's flip the stack over so $$$m_{new} = n - m_{old} \le \frac{n}{2}$$$.

Then, let's solve this problem: Does there exist a number $$$c$$$, such that $$$c \cdot { 1...t } \equiv {1...t} \pmod N$$$? In other words, can we find a set $$${1...t}$$$ that is closed under multiplication by $$$c \pmod N$$$? ($$$t \ge 1$$$, $$$c \ge 2$$$, since $$$c=1$$$ just perfectly sorts it)

We show that this is impossible for $$$t \lt \frac{N}{2}$$$ (remember $$$N$$$ is odd).

Suppose such $$$c$$$ and $$$t$$$ did exist. Then let's consider:

• If $$$c \gt \frac{N}{2}$$$, then $$$1$$$ has to be in the set, and thus $$$c \gt \frac{N}{2}$$$ has to be in the set, but that's not possible since $$$t \lt \frac{N}{2} \lt c$$$.
• If $$$c \lt \frac{N}{2}$$$ and $$$ct \lt N$$$, then consider $$$t$$$, which maps to $$$ct$$$, and $$$ct \lt N$$$, so $$$ct \bmod N \gt t$$$, so $$$ct$$$ is not in the set and that's another contradiction.
• If $$$c \lt \frac{N}{2}$$$ and $$$ct \ge N$$$, then consider the sequence $$$c, 2c, 3c, ...$$$. Because $$$c \lt \frac{N}{2}$$$, there will exist some $$$d$$$ where $$$\frac{N}{2} \lt cd \lt N$$$. That's because the window strictly between $$$\frac{N}{2}$$$ to $$$N$$$ has size $$$\left\lfloor \frac{N}{2} \right\rfloor$$$, and if $$$c \le \left\lfloor \frac{N}{2} \right\rfloor$$$, then you can't "skip" over this window. Also the $$$ct \ge N$$$ condition guarantees that $$$d \le t$$$, so $$$d$$$ is in the set. Then, since $$$t \lt \frac{N}{2}$$$, $$$cd$$$ can't be in the set, and we have a contradiction.

To use the lemma to solve the problem, we have $$$m \le \frac{n}{2}$$$ white chips occupying indices $$$0, ..., m-1$$$. This is exactly like our multiplication problem with $$$t = m-1 \lt \frac{N}{2}$$$. And we allow any value $$$c$$$, which is actually stronger than we need (under real operations, $$$c$$$ can only be powers of 2 $$$\bmod N$$$).

Thus, our lemma tells us that no $$$c \ge 2$$$ exists that permutes our white chips $$${1...t}$$$ onto themselves $$${1...t}$$$. Tthe only solution is $$$c=1$$$, which fully sorts them too.

Bonus: if we split the stack into thirds and shuffled them together that way ($$$f(x) = 3x \bmod N$$$), the same reasoning would apply!