Sort a small stack
Input
stack = [3, 1, 4, 2] # top is 2 (last element)
Output
[4, 3, 2, 1]
After sorting, the smallest element (1) should be on top (end of list). The list reads bottom->top: 4,3,2,1.
Full lesson preview
Sort a stack with one auxiliary stack
Sort a stack using only one extra stack and no other data structures.
Python practice16 minStacks & QueuesIntermediateLast updated March 27, 2026
Problem statement
You are given a stack represented by a Python list where the end of the list is the top of the stack (pop() / append()). Implement sort_stack(stack) that returns a new list representing the sorted stack where the smallest element is at the top (end of the list). You may use one additional stack (another list) and a limited number of primitive variables, but you may not use other data structures like arrays for bulk storage, nor built-in sort. The result should be a list representing the sorted stack (same representation as input).
Task
Given a stack represented as a list (top is the last element), sort it so the smallest element is on top using one auxiliary stack and standard stack operations.
Examples
Input format
One argument: stack (list of integers). Example: sort_stack([3,1,2])
Output format
A list representing the sorted stack with smallest element at the end (top).
Constraints
- You may only use one auxiliary stack (list) and a few scalar variables.
- Do not use built-in sorting routines.
- Aim for O(n^2) time in worst case and O(n) extra space for the auxiliary stack.
Samples
Sample 1
Input
stack = [1, 2, 3, 4]
Output
[4, 3, 2, 1]
Regardless of initial order, after sorting the smallest element is at the top (end).