Sort a stack using recursion

Medium

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: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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);
}