Sort a stack using recursion
Problem
Sort a stack so the largest element is on top, using only push, pop, peek and recursion.
Example 1
Input: (bottom → top) [34, 3, 31, 98, 92, 23] Output: [3, 23, 31, 34, 92, 98]
Also asked as: Sort a Stack using recursion
Test cases
Case 1
Input: [34,3,31,98,92,23] Expected: [3,23,31,34,92,98]
Case 2
Input: [2,2,1] Expected: [1,2,2]
Case 3
Input: [1] Expected: [1]
Case 4
Input: [] Expected: []
View solutionHide solution1 approach
1. Recursively sort, then insert in order
Time O(n²)Space O(n)
Pop the top, sort the rest, then insert the top back into its sorted position (another recursive helper).
function sortStack(s) { if (s.length === 0) return; const top = s.pop(); sortStack(s); sortedInsert(s, top);}function sortedInsert(s, x) { if (!s.length || s[s.length - 1] <= x) { s.push(x); return; } const t = s.pop(); sortedInsert(s, x); s.push(t);}