Interleaving algorithm for 2 stacks

Suppose I have two stacks $$ and $$ and a third stack of size $m+n$.
I want to have the third stack in the following manner, $$$$ for $$m>n$$
This was easy to do if the two initial stacks were not size constrained. But if the two stacks are size constrained, I am in a fix.

Is it even possible to interleave the elements of the two stacks into a third stack in constant space? Also what would be the minimum number of moves to do this? I know using recursion this can be reduced to Tower of Hanoi variant, but what about a non-recursive algorithm?

Note: I found a better technique which I give in a separate answer, which is more general, faster and simpler, though the complexity results remain somewhat similar. I chose to leave this answer rather than replace it, as it may be interesting to compare, and both solutions were too long for a single answer.

Let A, B and C be the three stacks.
I assume that the top of A and B are on the small index side.

I note (X,Y,p) the transfer of p elements from the top of X to the top
of Y. This has of course the effect of inverting the order of these p
elements, and has a cost p.

Let q and r the quotient and remainder of the integer division of m by
n. Thus m=q*n+r.

Pseudocode for the interleaving

% transfer of the m-n unmatched tail by chunk of n elements
For i from 1 by 1 to q-1 do
  % transfer the bottom n elements remaining in A
  (B,C,n)
  (A,C,m-i*n)
  (A,B,n)      % bottom n
  (C,A,m-i*n)
  (B,C,n)      % bottom n
  (C,A,n)      % bottom n
  (C,B,n)
  (A,C,n)      % bottom n
  end loop
if r≠0 then
  % transfer the remaining r elements of the umatched tail
  (B,C,n)
  (A,C,n)
  (A,B,r)      % bottom r
  (C,A,n)
  (B,C,r)      % bottom r
  (C,A,r)      % bottom r
  (C,B,n)
  (A,C,r)      % bottom r
  end if

% Now we have transferred the extra elements of A at the bottom of C.
% We have only 2n slots available in C, for intertwining A and B.
% But we have m-n free slots in A.

(A,C,n)   % rest of A inverted in C
(B,A,n)   % B inverted in A
k=n       % number of remaining elements of each stack still to be transferred
t=m-k     % available space in A to do the transfer
while k>0 do
  t=min(k,t)
  (C,A,t)   % last t of A in direct order in A
  (C,B,k-t) % top rest of A in B in direct order
  (A,B,t)   % last t of A inverted in B
  For i from 1 by 1 to t do    % intertwin in C last t elements of remainder
    (A,C,1)
    (B,C,1)
    end loop
  (B,C,k-t) % top rest of A inverted in C
  k=k-t
  t=2t
  end  loop

Complexity

I am only counting the number of moves. It actually gives the
complexity since the control statements introduce only a constant
factor on the moves and the number of moves is polynomial.

For one iteration of the first loop : $6n+2(m-i\times n)$

Hence the cost of the loop is $\sum_{i=1}^{q-1}6n+2(m-i\times n)$
= $(q-1)(6n+2m)-2nq(q-1)/2$ = $(q-1)(6n+2m-nq)$ = $(q-1)(6n+2m-(m-r))$
= $(q-1)(6n+m+r)$

The cost of the following conditional is at worst $4(n+r)$

So the total cost for the last $m-n$ elements of stack A is majored by
$q(6n+m+r) \leq q(7n+mn/n) \leq 7m+m^2/n$

The cost of transferring the tail of A is quadratic in $m$ when $n$ is
constant, as B becomes too small with increasing values of $m$ to do
the tranfer in a fixed number of passes over the whole stack. The
linear decrease of the remaining part to be transferred does not help
enough.

Things are however better with the parts of the two stacks that must
be intertwined.

There is a first cost of $2n$.

The cost of one iteration of the loop is $2t+2(k-t)+2t$, the cost of
the inner loop being $2t$. So this makes a total of $2(k+t)$.

If $m\geq 2n$ then the loop is executed only once, with $k=t=n$, hence
the cost is $4n$. Note that $4n\leq 2m$ in this case.

Otherwise we start the loop with $k=n$ and $t=m-n$, so that we
have $k+t=m$. But the update k=k-t; t=2t at the end of the loop
preserve this property as an invariant. So each iteration actually
costs $2(k+t)=2m$, except possibly the last one, since $t$ may be
reduced by the statement t=min(k,t), thus lowering the cost of that
last iteration. Note that, in this case, $2m\leq 4n$.

Since $t$ doubles at each iteration, but will not be greater than $n$,
the number of iterations is at worse $1+\log_2 n$, when $t$ starts with
value 1. Note that there must be at least one iteration when $n=1$
(though it could be simplified), in which case $\log_2 n=0$.

But the initial value of $t$ is actually $min(n,
m-n)$. Since it would take $\log_2 min(n, m-n)$ iterations to reach that value,
starting from 1, the actual number of iterations is $1+\log_2 n - \log_2
min(n, m-n) = $1+log_2 \frac{n}{min(n, m-n)}$

Hence the total cost for this part is less than $2n+4n(1+\log_2 \frac{n}{min(n, m-n)})$

So, the overall complexity in stack moves is $O(m^2/n+n(1+\log
\frac{n}{min(n, m-n))})$

In particular the complexity is linear in $n$ or $m$ when the ratio
$h=m/n$ remains constant.

This is obvious for the first term $m^2/n=h^2n$.

For the second term, we have
$min(n,m-n)=min(n,n(h-1))=n min(1, h-1)$. Hence $n(1+\log
\frac{n}{min(n, m-n))})= n(1+\log\frac{1}{min(1, h-1))})$

StackExchange Computer Science Q#28980, answer score: 3