Log inSign up
mediumGeeksforGeeksNot Started

Sort a Stack using Recursion

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Stack
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a stack of integers, sort the elements in the stack in ascending order (such that the greatest element is on top of the stack) using recursion.

You are NOT allowed to use any loop constructs like for, while, or auxiliary data structures (like arrays, vectors, or second stacks). You may only use standard stack operations (push, pop, top/peek, and isEmpty) along with the system call stack via recursion.

Example 1 · Small Stack:

Input: st = [3, 2, 1] (top is 1)
Output: [1, 2, 3] (top is 3)
Explanation: After sorting, elements from bottom to top are 1, 2, 3 with 3 at the top.

Example 2 · Mixed Integers:

Input: st = [11, 2, 32, 3, 41] (top is 41)
Output: [2, 3, 11, 32, 41] (top is 41)
Explanation: Elements sorted in ascending order from bottom to top: 2 at bottom, 41 at top.

Constraints:

  • 1 <= stack.size() <= 1000
  • -105 <= element <= 105

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master using the system call stack as an implicit LIFO storage buffer.
  • Understand recursive insertion mechanics in constrained data structures.
  • Analyze recurrence relations T(N) = T(N-1) + O(N) = O(N2).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Stack manipulation without loops or auxiliary data structures
  • Problem explicitly asks for recursive stack re-ordering
  • Decomposing sorting into recursive pop and recursive insert

Algorithmic Decision Tree:

  • Step 1: Pop top element x, recursively sort remaining n-1 elements.
  • Step 2: Insert x in sorted position into the already sorted n-1 elements via helper function sortedInsert.

Connected Patterns:

Reverse a Stack using RecursionInsert at Bottom of Stack

1. Array Transfer & Standard Sort

Intuition

Empty the stack into an array or list. Sort the list in ascending order using standard library sort O(N log N). Then push all elements from index 0 to N-1 back into the stack so that the maximum element rests at the top.

When to apply: Baseline comparison when loop/auxiliary storage constraints are not enforced.

Algorithm

  1. Pop all elements from stack into a dynamic array arr.
  2. Sort arr in ascending order.
  3. Push sorted items back into stack in order.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3#include <vector>
4#include <algorithm>
5
6using namespace std;
7
8class Solution {
9public:
10 void sortStackArray(stack<int>& s) {
11 vector<int> arr;
12 while (!s.empty()) {
13 arr.push_back(s.top());
14 s.pop();
15 }
16 sort(arr.begin(), arr.end());
17 for (int v : arr) {
18 s.push(v);
19 }
20 }
21};
22
23int main() {
24 stack<int> s;
25 s.push(11); s.push(2); s.push(32); s.push(3); s.push(41);
26 Solution sol;
27 sol.sortStackArray(s);
28 while (!s.empty()) {
29 cout << s.top() << " ";
30 s.pop();
31 }
32 cout << endl;
33 return 0;
34}

Time & Space Complexity

  • Time complexity: O(N log N) — Draining takes O(N), standard sort takes O(N log N), and reloading takes O(N).
  • Space complexity: O(N) — Auxiliary array stores all N elements.

2. Iterative Approach with Auxiliary Stack

Intuition

While input stack is not empty, pop element x. While temp stack top is greater than x, pop from temp stack and push back to input stack. Push x to temp stack. Finally transfer back to original stack.

When to apply: When iteration is permitted but only standard stack operations and stack data structures are allowed.

Algorithm

  1. Create empty temporary stack tmpStack.
  2. While input stack s is not empty:
  3. - Pop tmp = s.pop().
  4. - While tmpStack is not empty and tmpStack.top() > tmp:
  5. - Pop from tmpStack and push to s.
  6. - Push tmp to tmpStack.
  7. Transfer all elements from tmpStack back to s.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3
4using namespace std;
5
6class Solution {
7public:
8 void sortStackIterative(stack<int>& s) {
9 stack<int> tmpStack;
10 while (!s.empty()) {
11 int tmp = s.top();
12 s.pop();
13 while (!tmpStack.empty() && tmpStack.top() > tmp) {
14 s.push(tmpStack.top());
15 tmpStack.pop();
16 }
17 tmpStack.push(tmp);
18 }
19 while (!tmpStack.empty()) {
20 s.push(tmpStack.top());
21 tmpStack.pop();
22 }
23 }
24};
25
26int main() {
27 stack<int> s;
28 s.push(11); s.push(2); s.push(32); s.push(3); s.push(41);
29 Solution sol;
30 sol.sortStackIterative(s);
31 while (!s.empty()) {
32 cout << s.top() << " ";
33 s.pop();
34 }
35 cout << endl;
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(N^2) — In the worst case (reverse sorted order), elements are transferred back and forth quadratic times.
  • Space complexity: O(N) — Requires a secondary stack of size N.

3. Pure Recursion (sortStack + sortedInsert)

Intuition

Base case: empty stack is already sorted. Recursive step: pop top element x, recursively sort remainder of stack, then call sortedInsert(s, x) which inserts x into its correct sorted location recursively.

When to apply: The exact standard optimal interview solution satisfying strict constraints of zero loops and zero extra data structures.

Algorithm

  1. Function sortStack(s):
  2. 1. Base case: If stack is empty, return.
  3. 2. Pop top element top = s.pop().
  4. 3. Recursively call sortStack(s).
  5. 4. Call sortedInsert(s, top) to place top into sorted position.
  7. Function sortedInsert(s, element):
  8. 1. Base case: If stack is empty OR element > s.top(), push element and return.
  9. 2. Pop temp = s.pop().
  10. 3. Recursively call sortedInsert(s, element).
  11. 4. Push temp back onto stack.

Recursive Stack Sort Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Initial stack has bottom: 3, middle: 1, top: 2
Visual state
Values and pointers at this exact step
stack
TOP
3
1
2
Push adds to the top · Pop removes from the top
Variables at this step
callStack
["sort(3)","sort(1)","sort(2)"]
Why this step matters

Initial stack has bottom: 3, middle: 1, top: 2. Pop all recursively until empty.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <stack>
3
4using namespace std;
5
6class Solution {
7 void sortedInsert(stack<int>& s, int element) {
8 if (s.empty() || element > s.top()) {
9 s.push(element);
10 return;
11 }
12 int top = s.top();
13 s.pop();
14 sortedInsert(s, element);
15 s.push(top);
16 }
17
18public:
19 void sortStack(stack<int>& s) {
20 if (s.empty()) return;
21 int top = s.top();
22 s.pop();
23 sortStack(s);
24 sortedInsert(s, top);
25 }
26};
27
28int main() {
29 stack<int> s;
30 s.push(11); s.push(2); s.push(32); s.push(3); s.push(41);
31 Solution sol;
32 sol.sortStack(s);
33 cout << "Top to bottom: ";
34 while (!s.empty()) {
35 cout << s.top() << " ";
36 s.pop();
37 }
38 cout << endl;
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(N^2) — For every element popped (N elements), sortedInsert makes up to O(N) recursive steps. Total time = 1 + 2 + ... + N = O(N2).
  • Space complexity: O(N) — Call stack reaches a maximum depth of N frames during sorting and sortedInsert.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Array Transfer & Standard SortO(N log N)O(N)Dump elements into array, sort with built-in sort, push back.Array memory allocation
2.Iterative Approach with Auxiliary StackO(N^2)O(N)Use while loops and secondary stack to insert in sorted order.Repeated element popping and re-pushing
3.Pure Recursion (sortStack + sortedInsert)OptimalO(N^2)O(N)Empty stack via recursion, insert each element back in sorted order.Recursion depth bounded by stack size

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Forgetting the base condition in sortedInsert (stack empty or element > stack.top()).

Pitfall 2:

Confusing whether top should be the minimum or maximum element.

Pitfall 3:

Trying to use an auxiliary stack when the interview problem explicitly restricts memory to the call stack.

Crucial Edge Cases to Validate:

  • Empty Stack: s = [] -> returns [] without error.
  • Single Element Stack: s = [5] -> popped, recursed on empty stack, inserted back as single item.
  • Already Sorted Stack: s = [1, 2, 3, 4] -> sortedInsert immediately pushes element on top with O(1) checks.
  • Reverse Sorted Stack: s = [4, 3, 2, 1] -> worst case where sortedInsert pops all elements to bottom.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clearly explain how the Call Stack acts as memory: Highlight that recursion stores popped elements in activation frames, effectively using the runtime stack.
  2. Write helper functions modularly: Separate sortStack and sortedInsert cleanly with single responsibilities.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the worst-case number of recursive calls made by sortedInsert on a stack of size k?

2.How can the sorting order be inverted (so smallest is on top)?

Back to DSA Sheet