A simpler and more general answer
Introduction
Since we do not know for sure from the OP where is the top of the stack, I am
proposing a solution that is insensitive to it, and can actually
answer his question for any type of interleaving, as long as it
preserve for the elements coming from a given stack the order that they had
in that stack.
The general idea is quite simple: we transfer elements from A or B to
C in any order corresponding to the desired interleaving. This will
produce the reverse order of the desired result in C. It has a cost of
exactly $m+n$ moves.
Then we are left with the problem of reversing the content of the
stack C, using A and B. This is the problem I will now address.
The algorithms proposed have complexity $\Theta(m^2/n)$, which is quadratic in $m$ when $n$ is constant, and linear in $m$ when the ratio $m/n$ is constant.
A simple twist in the second algorithm can double the speed.
These solutions do not require $m>n$, wich is
a hypothesis of the question. It also
works when $m=n$.
A somewhat more complexe version of this solution, now edited out and replaced by those given below, was initially inspired in part by the answers of ZeroUltimax and
Karolis Juodelė, which are both based on the idea of moving a single element
of the top of A or B to the bottom of C.
I am leaving posted my previous answer, which shows how complex a problem can
become, when starting on the wrong path. Separating issues can make things much simpler.
The problem of stack reversal
We have two empty stacks A and B, respetively of size $m$
and $n$. We assume, without loss of generality, that $m\geq n$.
We also have a stack C of size $m+n$. Note that there is no requirement that $m\neq n$.
Using only stack operations, and no extra memory for stack elements
other than A and B, we want to reverse the order of the content of C,
i.e. to end up with the same content in C in reverse order.
Notations used for the algorithms:
We note (X,Y,p) the transfer of a segment of p elements from the top of stack X to the top of stack Y. This has of course the effect of reversing the order of these p elements, and has a cost p.
For each segment we transfer in a stack X, we call it direct if it is in its original
order in C, and reverse when it is in reverse order. We comment each application of a transfer by specifying whether the transferred segment is in direct or reverse order after the transfer is performed.
A very simple stack reversal algorithm
The idea is to operate with segments of size n, taking care to inverse
their order, and to inverse the order of the elements they contain.
The comments indicate the order of the elements of the segment
transferred, just after tranfer. Initially all element are in C, in
direct order, which we want to reverse.
Pseudocode for the simple algorithm
r = m modulo n
if r==0 then r=n
q = (m-r)/n % not actually used; number of iterations is q+1
For i from m by -n do
(C,A,n) % reverse
(A,B,n) % direct
(C,A,i) % reverse
(B,C,n) % reverse - final position
if i≤n then
(A,B,r) % direct
(B,C,r) % reverse - final position
exit loop
(A,C,i) % direct
end loop
Complexity
We measure the complexity in number of moves of one element.
Each iteration costs $3n+2i$ moves, and there is an extra $r$ moves at the
last iteration.
There are $q+1$ iteration with $i=m-j\times n$ for $j\in[0,q-1]$.
So the total cost, i.e., number of moves, is:
$\begin{align*}
\mathcal{C} &= r+\sum_{j=0}^q 3n+2(m-jn) \\
&= r+(q+1)(3n+2m)-2n\sum_{j=0}^qj \\
&= r+(q+1)(3n+2m)-2nq(q+1)/2 \\
&= r+(q+1)(3n+2m-nq) \\
&= r+(q+1)(3n+2m-(m-r)) \\
&= r+(q+1)(3n+m+r) \\
&= 3nq+qm+qr+3n+m+2r \\
&= 3(m-r)+qm+qr+3n+m+2r \\
&= qm+qr+4m+3n-r \\
&= qm+(q-1)r+4m+3n \\
&= m(m-r)/n + r(m-r)/n +4m+3n-r \\
&= m^2/n-mr/n + mr/n-r^2/n +4m+3n-r \\
&= m^2/n - r^2/n +4m+3n-r \\
&= m^2/n - (r^2/n+r) +4m+3n
\end{align*}$
Since $r\in[1,n]$, the asymptotic complexity is $\Theta(m^2/n)$.
The algorithm is linear in $m$ when the ratio $m/n$ is constant. It is
quadratic in $m$ if $n$ is constant. Note also the number of moves
increases with the ratio $m/n$, in particular when $n$ gets smaller for
constant $m$, and the algorithm no longer works for $n=0$.
The coefficient of the main term is $1/n$ when the algorithm is
quadratic because $n$ is constant.
The result is of course the same for the initial interleaving problem,
as it take only a linear amount of extra moves.
An stack reversal algorithm that is twice as fast
The analysis of the previous algorithm shows there seem to be no way
of escaping the back and forth transfer of the bulk of the stack. But
the algorithm would be faster if we could do more work, whenever the
stack is thus moved between C and A. The limiting factor is the size
$n$ of the smaller stack B, which is the maximum that may be moved
together from one end of the stack content to the other end. But the
weakness of the previous algorithm is that it works on only one end,
building the final reversed stack at the bottom of C. We now propose
to use the same strategy, but working on both end at the same time,
building the lower half of the final reversed stack at the bottom of C
and the upper half in direct order at the bottom of A. This allows to
process $2n$ elements for each back and forth movement of the stack,
and will thus double the speed, at least when $m/n$ is large, which is
precisely what makes the algorithm otherwise slower.
The stacks C and A have then a symmetrical role for most of the
algorithm.
The faster algorithm in pseudocode
s = m+n modulo 2n
if s==0 then s=2n
t = (m+n-s)/2n % number of iterations, not actually used
For i from m by -2n while i>n do
(C,A,n) % reverse
(A,B,n) % direct
(C,A,i) % reverse
(B,C,n) % reverse - final position in C
(A,B,n) % direct
(A,C,i-n) % direct
(B,C,n) % reverse
(C,A,n) % direct - final position in A
end loop
if s≥n then
(C,A,n) % reverse
(A,B,n) % direct
(C,A,s-n) % reverse
(B,C,n) % reverse - final position in C
(A,B,s-n) % direct
(B,C,s-n) % reverse - final position in C
else
(C,A,s) % reverse
(A,B,s) % direct
(B,C,s) % reverse - final position in C
end if
(A,C,t*n) % reverse - push back into C the part of the work accumulated in A
Complexity
The cost of one iteration is $5n+2i$ where $i=m-2nj$ for $j\in[0,t-1]$
So the cost of the loop is
$\begin{align*}
\mathcal{C}_{loop} &= \sum_{i=0}^{t-1} 5n+2(m-2nj) \\
&= t(2m+5n) -4n(t(t-1)/2)) \\
&= t(2m+5n-2n(t-1)) \\
&= t(2m+7n-2nt)
\end{align*}$
Since $2nt=(m+n-s)$ we have
$\begin{align*}
\mathcal{C}_{loop} &= t(2m+7n-(m+n-s) \\
&= t(m+6n+s)
\end{align*}$
The cost of the conditional is
$\mathcal{C}_{if}$ = $3s$ in both branches
And the final transfer of about half the stack from A to C costs $nt$,
since there were $t$ iteration storing $n$ element each in A.
So the total cost is
$\begin{align*}
\mathcal{C} &= t(m+6n+s)+3s+nt \\
&= t(m+s)+3s+7nt \\
&= t(m+s)+3s+7(m+n-s)/2 \\
&= t(m+s)+(7m+7n-s)/2 \\
&= tm+(t-1/2)s+7(m+n)/2 \\
&= m(m+n-s)/2n + ((m+n-s)/2n-1/2)s +7(m+n)/2 \\
&= m^2/2n+m/2+ms/2n + ms/2n+s/2-s^2/2n-s/2 +7m/2+7n/2 \\
&= m^2/2n+4m +ms/n - s^2/2n +7n/2 \\
&= m^2/2n+ (4+s/n)m - s^2/2n +7n/2
\end{align*}$
Since $r\in[1,2n]$, the asymptotic complexity is $\Theta(m^2/n)$.
The algorithm is linear in $m$ when the ratio $m/n$ is constant. It is
quadratic in $m$ if $n$ is constant. Note also the number of moves
increases with the ratio $m/n$, in particular when $n$ gets smaller for
constant $m$, and the algorithm no longer works for $n=0$.
Comparison with the simpler algorithm
Note however that the term of the cost that determine this complexity
when quadratic, which is the worse situation, is $m^2/2n$. It
coefficient $1/2n$ is half the coefficient for the previous algorithm,
so that this algorithm is asymptotically faster than the previous
one by 50% when it is quadratic.
The result is of course the same for the initial interleaving problem,
as it take only a linear amount of extra moves, actually $m+n$ moves.
