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?