Algorithm for a deck manipulation

Question

Let's say you have a randomised deck of $N$ different cards. An $M$-action ($M\le N$) is defined as follows: you look at the top $M$ cards of the deck, put as many of them as you choose on top of the deck, and the rest on the bottom, each time in any order you choose. How many $M$-actions does it take to arrange an $N$-card deck into a given order?

Answer 1

Let's call the operation of looking at the top $M$ cards and placing them on the top and/or bottom of the deck in arbitrary order scrying. There are $N!$ different states that the deck can be in initially, and each iteration of scry M presents $(M+1)!$ choices of where to place the cards. So a simple lower bound is that, in the worst case, it must take $\lceil{\log(N!)/\log((M+1)!)}\rceil$ iterations to sort the deck. This is conservative, as seen by considering the $M=1$ case, where the task may not even be achievable.

A better lower bound is obtained by picturing the cards in a circle, with a pointer between the bottom and top cards. Then the operation scry M becomes: rearrange the $M$ cards clockwise from the pointer, in place, then move the pointer up to $M$ places clockwise. To place the cards in the correct order, ignoring the position of the pointer, must take $\lceil{\log((N-1)!)/\log(M!)}\rceil$ operations in the worst case.

On the other hand, it can't take more than $N^2/(M-1)$ iterations, as demonstrated by the following algorithm. Assume without loss of generality that the target order is $\{1,2,...N\}$. For $i=1,2,...N$: move the pointer clockwise by $M$ positions per iteration until card $i$ is in the window, then move card $i$ and the pointer clockwise by $M-1$ positions per iteration until the $i$-th position is in the window, then deposit card $i$ in the $i$-th position and increment $i$. This takes at most $N/(M-1)$ iterations per correctly placed card. This can be improved by carrying along the next $k$ cards instead of just one (reducing the distance the pointer can be moved per iteration to $M-k$). With this variation, it takes at most $N/(M-k)$ iterations per $k$ correctly placed cards, for a total count of $N^2/(k(M-k))$ iterations, which is minimized at $4N^2/M^2$ by taking $k=M/2$.

Because of the finite "range" of the operation, I would conjecture that the actual complexity is $\Theta(N^2)$, i.e., that this upper bound is asymptotically tight, and that it is achieved when the deck is shuffled into the reverse of its target order. I'm less sure about the exact dependence on $M$.

---

Update: For $M=2$ and $2\le N\le10$, the maximum number of operations required is $1,1,3,5,7,11,14,19,23.$ This is reasonably well fit by $\alpha N^2$, where $\alpha$ is around $0.2-0.25$. The entropy lower bound $\lceil{\log((N-1)!)/\log(M!)}\rceil$ with the same parameters is $0,1,3,5,7,10,13,16,19.$