<p>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.</p>

<p>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.</p>

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

<p>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</p>

<p>If line $i$ is of the form</p>

<p>if $X_u&lt;X_v$ then goto $i_1$ else goto $i_2$</p>

<p>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)$.</p>

<p>If line $i$ is of the form </p>

<p>$X_1 \leftarrow tail(X_2)$, goto line $i'$</p>

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

<p>If line $i$ is of the form </p>

<p>$print(head(X_u))$, goto line $i'$</p>

<p>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.</p>

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

CC BY-SA 3.0
2014-03-10T07:40:14.503Z
2014-03-10T07:40:14.503Z
Siddharth
<p>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:</p>

<p>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.</p>

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

<p>(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)</p>

<hr>

<p>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:</p>

<p>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.</p>

<p>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)$.</p>

CC BY-SA 3.0
2014-02-28T08:34:59.670Z
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?
Siddharth
CC BY-SA 3.0
2014-02-28T10:12:33.570Z
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?
cero
CC BY-SA 3.0
2014-02-28T11:59:01.260Z
You can't push anything on top of other items as explained in the question.
Kaveh
CC BY-SA 3.0
2014-02-27T11:04:43.247Z
2014-02-27T11:04:43.247Z
cero
<p>Consider the following setting:</p>

<ul>
<li>we are given a stack $s$ which contains $n$ items.</li>
<li>we can use a constant $O(1)$ number of extra stacks.</li>
<li>we can apply the following operations on these stacks:
<ol>
<li>check if a stack is empty,</li>
<li>compare the top items of two stacks,</li>
<li>delete the top item in a stack,</li>
<li>print the top item in a stack,</li>
<li>copy the top item of a stack into another stack,</li>
<li>copy the content of one stack to another stack.</li>
</ol></li>
</ul>

<p>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).</p>

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

<pre><code>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
</code></pre>

<p>Can we do better?</p>

<blockquote>
  <p>Is there a program that prints the sorted list of the items in the stacks 
  using only $O(n\log n)$ comparisons?</p>
</blockquote>

CC BY-SA 3.0
2014-02-20T08:36:31.267Z
I don't think it's possible to print the sorted list given the allowed operations. According to the register machine model, the first entry printed must be one of the first element of some register. Thus if the smallest element is at the end of one register, we can't possibly print it out firstly as it should be.
caozhu
CC BY-SA 3.0
2014-02-20T08:37:23.903Z
so you're not even allowed a swap operation ?
Suresh Venkat
CC BY-SA 3.0
2014-02-20T09:34:16.230Z
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?
AturSams
CC BY-SA 3.0
2014-02-20T11:22:53.130Z
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)$).
Kaveh
CC BY-SA 3.0
2014-02-21T05:41:16.460Z
@SureshVenkat -- No, we are not even allowed a swap operation
Siddharth
CC BY-SA 3.0
2014-02-21T05:52:01.583Z
Such read-only sorting programs do exist. We can implement a binary function that, given a list and a single character $c$, computes the minimum value in the list greater than $c$.

Then we can write a program which (roughly) computes the minimum $a$ of the list, prints it, computes the minimum of the list larger than $a$, prints it, and so on. 



@ArthurWulfWhite -- Yes, exactly, they are stacks in which we are forbidden from pushing anything onto a stack
Siddharth
CC BY-SA 3.0
2014-02-21T06:12:09.687Z
Do you want to use $O(1)$ registers? Otherwise the problem trivializes, as commented by Kaveh.
Yuval Filmus
CC BY-SA 3.0
2014-02-21T10:23:44.337Z
How many stacks do you have? It sounds like the worst case scenario is going to be O(n^2) with O(1) stacks.
AturSams
CC BY-SA 3.0
2014-02-22T05:44:24.497Z
Thanks all for bringing my attention to this. Yes I assume a constant number of registers. I will modify the question accordingly.
Siddharth
CC BY-SA 3.0
2014-02-22T07:12:03.693Z
Thanks @Kaveh! In my mind, I'm imagining the input as a single stack with $n$ elements. Where do your $m$ stacks come from?
Siddharth
CC BY-SA 3.0
2014-02-22T07:13:55.057Z
You are welcome. I thought that we are given a number of stacks, not just one, I will fix it.
Kaveh
CC BY-SA 3.0
2014-02-25T09:11:59.697Z
The answer to "can we do better" is easy: there is a $O(n^{3/2})$ algorithm which applies selection sort to successive blocks of size $O(n^{1/2})$, merging at each step the current block with the list of already sorted elements. Dunno about the feasibility of the $O(n\, \log n)$ algorithm, though.
Andrea Farruggia
CC BY-SA 3.0
2014-02-28T12:03:21.497Z
@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?
Kaveh
CC BY-SA 3.0
2014-03-01T23:04:50.350Z
@Kaveh: I thought it was allowed to push elements into those $O(1)$ stacks (which would allow a simple $O(n \log n)$ mergesort implementation along the lines of the answer given below, but I was too lazy to describe it in the comment), I overlooked the passage where it is stated it isn't allowed to do that. My bad.
Andrea Farruggia
<ds.algorithms><sorting>
Sorting using read-only stacks
Siddharth
# Sorting using read-only stacks

(Asked by: username_0 on 2014-02-20)

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 > 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?

**Tags:** ds.algorithms, sorting
> **Comments:**
> **username_1**: I don't think it's possible to print the sorted list given the allowed operations. According to the register machine model, the first entry printed must be one of the first element of some register. Thus if the smallest element is at the end of one register, we can't possibly print it out firstly as it should be.  
> **username_2**: so you're not even allowed a swap operation ?  
> **username_3**: 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?  
> **username_4**: 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)$).  
> **username_0**: @SureshVenkat -- No, we are not even allowed a swap operation  
> **username_0**: Such read-only sorting programs do exist. We can implement a binary function that, given a list and a single character $c$, computes the minimum value in the list greater than $c$.  Then we can write a program which (roughly) computes the minimum $a$ of the list, prints it, computes the minimum of the list larger than $a$, prints it, and so on.     @ArthurWulfWhite -- Yes, exactly, they are stacks in which we are forbidden from pushing anything onto a stack  
> **username_5**: Do you want to use $O(1)$ registers? Otherwise the problem trivializes, as commented by Kaveh.  
> **username_3**: How many stacks do you have? It sounds like the worst case scenario is going to be O(n^2) with O(1) stacks.  
> **username_0**: Thanks all for bringing my attention to this. Yes I assume a constant number of registers. I will modify the question accordingly.  
> **username_0**: Thanks @Kaveh! In my mind, I'm imagining the input as a single stack with $n$ elements. Where do your $m$ stacks come from?  
> **username_4**: You are welcome. I thought that we are given a number of stacks, not just one, I will fix it.  
> **username_6**: The answer to "can we do better" is easy: there is a $O(n^{3/2})$ algorithm which applies selection sort to successive blocks of size $O(n^{1/2})$, merging at each step the current block with the list of already sorted elements. Dunno about the feasibility of the $O(n\, \log n)$ algorithm, though.  
> **username_4**: @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?  
> **username_6**: @Kaveh: I thought it was allowed to push elements into those $O(1)$ stacks (which would allow a simple $O(n \log n)$ mergesort implementation along the lines of the answer given below, but I was too lazy to describe it in the comment), I overlooked the passage where it is stated it isn't allowed to do that. My bad.  

---

## 2 answers

### Answer by username_0 on 2014-03-10. Score: 1

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

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


---

### Answer by username_7 on 2014-02-27. Score: 0

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

> **Comments:**
> **username_0**: 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?  
> **username_7**: 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?  
> **username_4**: You can't push anything on top of other items as explained in the question.  

---

