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:
    1. check if a stack is empty,
    2. compare the top items of two stacks,
    3. delete the top item in a stack,
    4. print the top item in a stack,
    5. copy the top item of a stack into another stack,
    6. 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 > last and w.top < 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?

  • 2
    $\begingroup$ It sounds like the registers behave like stacks? It sounds like you are talking about push and pop operations. Is that your questions? How would you sort a stack by using several stacks and stack operations? $\endgroup$ – wolfdawn Feb 20 '14 at 9:34
  • 2
    $\begingroup$ With $n$ registers you can: just put every number in one register ($O(n)$) and then apply a usual sorting algorithm ($O(n \lg n)$). $\endgroup$ – Kaveh Feb 20 '14 at 11:22
  • 1
    $\begingroup$ Do you want to use $O(1)$ registers? Otherwise the problem trivializes, as commented by Kaveh. $\endgroup$ – Yuval Filmus Feb 21 '14 at 6:12
  • 1
    $\begingroup$ You are welcome. I thought that we are given a number of stacks, not just one, I will fix it. $\endgroup$ – Kaveh Feb 22 '14 at 7:13
  • 2
    $\begingroup$ @akappa, are you sure that can be used in this seeing? We can't keep any arbitrary lost of size larger than 1. Don't you need to store the sorted blocks? $\endgroup$ – Kaveh Feb 28 '14 at 12:03

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<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)$


Are you able to count elements? Then, I think, there is a fairly easy Mergesort implementation. If you were able to put additional symbols on the stack you could solve it with 3 stacks like this:

If we have only one element, the list is already sorted. Now assume we have already sorted the top half of the stack. We can copy the top half (in reverse order) to the second stack and place a separation symbol on top of it. Now we have again 3 Stacks (since we can ignore the already sorted symbols below the separation symbol) and can sort the lower half. Finally we can copy the sorted lower half to a third stack in reverse order and merge both halfs back to the original stack.

All operations cost linear time, therefore we have sorted the list in $O(n \log n)$

(Note, that we need stacks of size $n \log n$ because of the separation symbols, but this can be easily corrected by using another stack)

Since you can't put new elements on the stack you may get problems at the separation points. To solve this you may do the following with some additional stacks:

Copy the top $n-2^{\lfloor \log n\rfloor}$ elements to an additional stack, then proceed with the remaining elements as before. Now you know exactly the number of elements you need to consider in each step and therefore don't need any separation symbols.

Finally repeat the procedure with the additional elements at most $\log n$ times and merge them to the original stack in linear time. Sorting the stacks costs, for some constant $c$, at most $cn \log n+c\frac{n}{2} \log \frac{n}{2}+c\frac{n}{4} \log \frac{n}{4}+\ ... = O(n \log n)$ time, while merging costs an additional $O(n \log n)$.

  • $\begingroup$ I'm not sure I understand. How can we, for example, copy the top half on the stack in reverse order onto another stack when we can never push any element onto any stack? $\endgroup$ – Siddharth Feb 28 '14 at 8:34
  • $\begingroup$ We can not push any new element to a stack, but according to 5 we are able to push the top element of one stack to another. So copying the stack in reverse order requires at most linear time. So I suppose, that was not what you were asking for? $\endgroup$ – cero Feb 28 '14 at 10:12
  • $\begingroup$ You can't push anything on top of other items as explained in the question. $\endgroup$ – Kaveh Feb 28 '14 at 11:59

Your Answer

