161. Sort a Stack Using Recursion

Given a stack of n integers (given as space-separated values from bottom to top - the order they were pushed in), sort it using only recursive stack operations (push/pop/peek/isEmpty - no other data structure) so that popping the sorted stack yields values in ascending order (the smallest value ends up on top). Print the sorted stack's values from top to bottom.

Input: The input is a single line of space-separated integers, the stack's values from bottom to top (the order they were pushed in). Output: Print the sorted stack's values, space-separated, from top to bottom, with the smallest value on top.

1 <= n <= 10^4

This uses the exact same 'recursively empty, then reinsert' skeleton as both 'Reverse a Stack' and 'Insert at Bottom' - the only difference is the specific reinsertion RULE (sorted-position insertion here, versus always-at-the-bottom for the other two).

Sort a stack's elements (so popping yields ascending order) using only recursive stack operations. Brute force: Copy the elements into an array, sort the array with a standard algorithm, and rebuild the stack - this works but uses an explicit array, which this problem's recursive-only constraint disallows. Optimised: The 'recursively empty, then reinsert each value into a smaller ALREADY-SORTED stack' technique (similar to insertion sort's core idea, just implemented via recursion instead of an explicit loop and array) achieves sorting using only the call stack as implicit storage - a clean fit for the problem's specific constraint.

Pop the top element, recursively sort what remains below it, and then recursively insert the popped element back into its correct place in the now-sorted stack (by popping off any values smaller than it, recursing, inserting, then pushing those smaller values back on top). This is the standard, minimal 'sort a stack using only recursion' technique: every operation is expressed purely as push/pop/peek/isEmpty plus recursion, with no auxiliary array anywhere, and it reaches the same sorted result more directly (fewer redundant full passes) than the repeated-bubbling approach. Time: O(n^2) Space: O(n)

Using only the stack and recursion, repeatedly make a single recursive 'pass' that pops every element off, remembers the maximum seen, and pushes everything back except leaves the maximum at the very bottom by recursing to the base of the stack; doing this n times sinks the largest, then second largest, and so on to the bottom, leaving the stack sorted with the smallest on top. This obeys the 'only stack operations' constraint, unlike the brute approach, but it needs a full pass over the remaining unsorted portion for every one of the n elements placed. Time: O(n^2) Space: O(n)

Pop every element off the stack into an array, sort that array with any efficient comparison sort, then push the values back on in the order that leaves the smallest on top. This is the fastest of the three approaches in raw time complexity, since it uses an efficient general-purpose sort, but it steps outside the spirit of the exercise (and the stated constraint of using only push/pop/peek/isEmpty) by relying on an auxiliary array as scratch space rather than solving it with recursion alone. Time: O(n log n) Space: O(n)

1. Recursively pop everything off the stack down to empty. 2. On the way back up (unwinding), insert each popped value back in using a helper that keeps the stack SORTED as it inserts - this helper recursively pops any elements bigger than the value being inserted out of the way first, inserts the value, then pushes those bigger elements back on top. 3. The final result, unwound fully, is a sorted stack.

Time: O(n²) - similar to insertion sort's complexity, since each of the n insertions can require popping and re-pushing up to O(n) elements. Space: O(n) for the recursion call stack at the deepest point.

n = 1 (a single element, trivially sorted); duplicate values, as in the example's two 1s; n = 10^4, the upper bound, given that only recursive stack operations are allowed.

Be ready to connect this directly to INSERTION SORT's core idea (insert each new element into its correct position within an already-sorted portion) - recognizing that this is essentially insertion sort implemented recursively on a stack is a strong signal.