Given a stack of integers st[], sort the stack in ascending order, so that…

Concept — a stack can be reordered only through its top, so it is sorted by inserting one element at a time into an already-sorted stack.

A stack is not a random-access container. The only element it ever exposes is the one on top: a push puts a new element there, a pop removes it, and every element below stays unreachable until everything covering it has been removed. Any rule for sorting a stack must therefore be expressible purely in terms of that single visible position.

One rule fits that restriction exactly, and it is insertion sort read through the top of the stack. Suppose the elements underneath the top are already arranged so that they increase from the bottom upwards. Then the whole stack is finished by taking the one remaining element and sliding it into the height where it belongs among them. That turns a sorting problem of size n into a sorting problem of size n − 1 plus a single insertion, which is exactly the shape of a recursion.

The insertion obeys the same restriction. In a stack that increases from the bottom upwards, every element that belongs above an incoming value x already sits above the height where x has to go. Removing those elements one at a time exposes the correct height, x is pushed there, and the removed elements are pushed back in the reverse of the order they came off, which restores each of them to the height it had. Because they come back in reverse order and every one of them was greater than x, the stack still increases from the bottom upwards.

The two rules, stated once:

1. sort(S): if S holds fewer than two elements it is already sorted, so there is nothing to do.

2. sort(S): otherwise pop the top element t, sort the smaller stack that remains, then insert t into that sorted stack.

3. insert(S, x): if S is empty, or the element on top of S is not greater than x, push x — that is the height where x belongs.

4. insert(S, x): otherwise pop the top element u, insert x into what remains, then push u back on top.

The property that makes this correct is that insert(S, x) is only ever called on a stack that is already sorted, and it returns a stack that is sorted and holds one more element. sort(S) establishes that precondition by sorting the smaller stack before it inserts, so the property carries upward from the base case of fewer than two elements to the full stack.

Application — sorting the first example.

The input line 41 3 32 2 11 lists the stack from top to bottom, so from bottom to top the stack is 11, 2, 32, 3, 41. sort pops repeatedly until nothing is left, then inserts the popped elements back in the reverse of the order they were taken — the bottom element first. The insertions therefore happen in the order 11, 2, 32, 3, 41.

The finished stack reads 2, 3, 11, 32, 41 from bottom to top, so the smallest element 2 is at the bottom and the largest element 41 is at the top. Printing it from top to bottom gives 41 32 11 3 2, which is the required output line.

Cross-check — cost, recursion depth, and the shape of the printed answer.

Each insertion may have to remove every element already sitting in the sorted stack, so the total number of removals is bounded by 1 + 2 + … + (n − 1), which grows in proportion to n2. With n at most 103 that is roughly half a million elementary stack operations, comfortably inside the time limit, and it is the cost this problem is designed around. Depth is the other resource to watch, and it is smaller than it first looks: the two recursions never reach their maxima together, because while an insertion is working on a stack of k elements only the n − k outer sort calls are still waiting behind it, so the deepest the nesting ever gets is about n frames rather than about 2n. That is still around a thousand nested calls at the largest allowed size, so a language with a shallow default recursion limit needs that limit raised.

Two independent checks confirm any printed answer. Sorting only changes the heights of the elements, never which elements are present, so the printed line must be a rearrangement of the input line — and 41 32 11 3 2 uses exactly the values 41, 3, 32, 2, 11. The required arrangement is ascending from the bottom upwards while the printed listing runs from the top downwards, so the printed sequence must be non-increasing — and 41 ≥ 32 ≥ 11 ≥ 3 ≥ 2 is. Equal values are permitted by the constraints, which is why the insertion stops as soon as the element on top is not greater than x rather than only when it is strictly smaller; stopping at equality keeps the number of removals down and leaves duplicates next to each other.

Reading the elements into an ordinary array and calling a library sort would print the same line, because the judge compares only the printed output. What that shortcut does not exercise is the restriction this problem is about — reaching a buried element only by removing whatever covers it — which is why the insertion above is written using nothing but push and pop.