DSA interview question

Sort a Stack Using Recursion

Medium · Data structures · Topics: recursion, stack

The problem

A warehouse robot stacks crates in a column and can only touch the top crate: push, pop, or peek. The column must be rearranged so that the heaviest crate ends on top (ascending from bottom to top). There's no second column and no loops allowed in the controller, only recursion. The idea is the recursive version of insertion sort: pop the top, sort the rest recursively, then insert the popped crate into its correct place, which is itself a small recursion that temporarily pops the larger crates out of the way.

Example (bottom → top): [11, 2, 32, 3, 41] → [2, 3, 11, 32, 41].

Function signature

void sortStack(stack<int>& s);  // afterwards the largest element is on top

Test cases

Input (bottom → top)	Output (bottom → top)	Explanation
`[11, 2, 32, 3, 41]`	`[2, 3, 11, 32, 41]`	The largest is on top
`[3, 2, 1]`	`[1, 2, 3]`	A reversed stack
`[4, 4, 1, 4]`	`[1, 4, 4, 4]`	Duplicates
`[5]`	`[5]`
`[]`	`[]`

(Confirm: only push, pop, top and empty may be used; no loops and no extra data structure, only the recursion stack.)

How interviewers phrase it

"Sort a stack using recursion, so that the top has the greatest element" (GeeksforGeeks).
A common variant allows one extra stack and asks for an iterative solution instead.

Clarifying questions to ask

Should the largest element end up on the top or the bottom?
Are loops allowed, or only recursion?
Can I use another stack or an array? (Usually not.)

Follow-ups to expect

"What does insertSorted do?"
"Why is it correct?"
"What's the complexity?"
"Where are the elements stored while recursing?"
"Iterative version with one extra stack?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview