Sorting using read-only stacks Consider the following setting:


we are given a stack $s$ which contains $n$ items.
we can use a constant $O(1)$ number of extra stacks.
we can apply the following operations on these stacks:

check if a stack is empty,
compare the top items of two stacks,
delete the top item in a stack,
print the top item in a stack,
copy the top item of a stack into another stack,
copy the content of one stack to another stack.



Note that these are the only operations that are permitted. 
We cannot swap items and 
we are not allowed to push any item onto any of the stacks 
with the exception of copying the top item into a stack 
(after which the previous content of the target stack is discarded and 
it will only contain the copied item).

Here is an algorithm to sort the stacks with $O(n^2)$ comparisons:

last := empty
for i from 1 to n
  min := empty
  w := s
  while w is not empty
    if w.top &gt; last and w.top &lt; min
      min := w.top
    delete w.top
  print min
  last := min


Can we do better?


  Is there a program that prints the sorted list of the items in the stacks 
  using only $O(n\log n)$ comparisons?
I think I can now demonstrate a nontrivial lower bound. The idea is to implement any such program with a family of comparison branching programs. The `read-only' assumption means that our family of branching programs uses little, i.e. $O(\log n)$, space. Then we apply the lower bound $ST=\Omega(n^2)$ proved by Borodin et al. in "A Time-Space Tradeoff for Sorting on non-oblivious Machines." This gives us a $n^2/\log n$ lower bound for the time.

In a bit more detail: We can dispense with operation 5 above. Loosely speaking, if we can already compare the heads of two lists and print the head of a list, then there is no need for us to isolate the head of a list on a particular register. Assuming this, we see that every register in the machine only ever stores a final substring of the input.

Suppose our register program has $\ell$ lines of code and $k$ registers, $X_1,\dots,X_k$.

Fix $n$. We construct the comparison branching program for strings of length $n$ as follows. Create a node for each tuple $(i,d_1,\dots,d_k)$ where $1\le i\le \ell$  and $0\le d_1 ,\dots, d_k \le n$. The idea is, computations in the register machine correspond to paths in the branching program, and we're at node $(i,d_1 ,\dots, d_k)$ if we're at line $i$ in the register machine and the length of the string stored in $X_i$ is $d_i$. Now, we have to define the directed edges of the branching program

If line $i$ is of the form

if $X_u&lt;X_v$ then goto $i_1$ else goto $i_2$

then for all $d_1,\dots,d_k$, node $(i,d_1,\dots,d_k)$ is labelled by comparing the $d_u$-th and $d_v$-th element of input, and having the "true" edge go to $(i_1,d_1,\dots,d_k)$, and the "false" edge to $(i_2,d_1,\dots,d_k)$.

If line $i$ is of the form 

$X_1 \leftarrow tail(X_2)$, goto line $i'$

then there is an arrow from any node $(i,d_1,\dots,d_k)$ to $(i',d_2-1,\dots,d_k)$.

If line $i$ is of the form 

$print(head(X_u))$, goto line $i'$

then there is an arrow from any node $(i,d_1,\dots,d_k)$ to $(i',d_1,\dots,d_k)$ which is labelled by the $d_u$-th node of the input.

Hopefully these examples make it clear how I intend to construct my branching program. When all is said and done, this branching program has at most $\ell\cdot n^k$ nodes, so it has space $O(\log n)$