Sort a Stack Using a Temporary Stack

Problem Sort a stack ascending (smallest on top or bottom — fix the convention) using ONLY one auxiliary stack — no arrays, no recursion.

Input / Output

• Input: stack of ints. Output: the same stack, sorted.

Constraints

• Up to 10^4 elements; O(n^2) worst case is expected and accepted — the constraint is the data-structure discipline, not asymptotics.

Example

• [34,3,31,98,92,23] (top=23) → sorted stack [3,23,31,34,92,98].

Expected approach

• Insertion sort across two stacks: pop tmp from input; while aux.top > tmp (for ascending aux), move aux elements back to input; push tmp onto aux — aux stays sorted at all times (loop invariant — state it). Finally aux holds the sorted result. O(n^2) time, O(n) space. Probes: sort direction ↔ comparison direction, duplicates (use >=/> consistently), and the recursion-based variant (call stack as the hidden second stack) that the "no recursion" clause is deliberately excluding.