Introduction

Sorting a stack is a classic interview and data structure exercise because you only get top access through push and pop. Without random index access, standard array sort patterns do not apply directly. The usual solution uses one auxiliary stack and only legal stack operations.

Problem Constraints and Sorting Goal

Assume you are given one stack and can use another stack as temporary storage. Allowed operations are push, pop, peek, and empty check. The goal is often to place the smallest element on top, though some variants expect the largest on top.

For clarity in this article, we will sort so the smallest element ends up on top of the original stack.

Two-Stack Insertion Style Algorithm

The algorithm is similar to insertion sort:

1. Pop one element from input stack into temp.
2. Move larger elements from auxiliary stack back to input stack.
3. Push temp into auxiliary stack in sorted position.
4. Repeat until input stack is empty.
5. Move everything back from auxiliary to input.

Python example using lists as stacks:

1def sort_stack(input_stack):
2    aux_stack = []
3
4    while input_stack:
5        temp = input_stack.pop()
6
7        while aux_stack and aux_stack[-1] > temp:
8            input_stack.append(aux_stack.pop())
9
10        aux_stack.append(temp)
11
12    while aux_stack:
13        input_stack.append(aux_stack.pop())
14
15    return input_stack
16
17# Top of stack is right side of the list
18stack = [3, 5, 1, 4, 2]
19print("before:", stack)
20sort_stack(stack)
21print("after :", stack)

Output:

before: [3, 5, 1, 4, 2]
after : [5, 4, 3, 2, 1]

Because top is on the right, the final rightmost value 1 is the smallest item on top.

Step Through a Small Example

Take input stack right to left top order from [3, 5, 1, 4, 2]:

• Pop 2, aux becomes [2].
• Pop 4, aux top is 2, push 4, aux becomes [2, 4].
• Pop 1, move 4 and 2 back, then push 1 so aux becomes [1].
• Continue until input is empty.
• Move aux back to input to restore one sorted stack.

The key invariant is: auxiliary stack remains sorted at all times.

Complexity and Practical Use

Worst case time complexity is quadratic, written as O(n^2), because each element may move between stacks multiple times. Space complexity is linear, written as O(n), for the auxiliary stack.

Even with non optimal asymptotic complexity, this method is still useful when:

• You must respect strict stack interface constraints.
• Input size is moderate.
• Simplicity and correctness are more important than peak speed.

If you can access array indices directly, standard sort methods are usually faster and simpler.

Recursive Variant Without Explicit Second Stack

Some problem statements allow recursion and count the call stack as implicit storage. In that version, recursively pop all elements, then insert each element back into the correct sorted position.

1def sorted_insert(stack, value):
2    if not stack or stack[-1] <= value:
3        stack.append(value)
4        return
5
6    top = stack.pop()
7    sorted_insert(stack, value)
8    stack.append(top)
9
10
11def sort_stack_recursive(stack):
12    if not stack:
13        return
14
15    top = stack.pop()
16    sort_stack_recursive(stack)
17    sorted_insert(stack, top)
18
19
20stack = [3, 5, 1, 4, 2]
21sort_stack_recursive(stack)
22print(stack)

This variant is elegant but can hit recursion limits on large input in some languages.

Common Pitfalls

• Losing track of top orientation in examples, which makes result checks look wrong.
• Forgetting to move data back from auxiliary stack to original stack.
• Using comparisons in the wrong direction and ending with reverse order.
• Assuming recursion is free for very large stacks. Deep recursion may fail.
• Mixing queue operations with stack operations, which breaks constraints.

Summary

• Sort a stack under stack-only rules by using an auxiliary stack.
• Maintain a sorted invariant in the auxiliary stack as you process items.
• Move elements back to return a single sorted original stack.
• Expect O(n^2) time and O(n) additional space.
• Validate top direction in tests so order requirements are unambiguous.