Sort a Stack

Problem

Sort the values of a stack using only stack operations.

values is the current stack from bottom to top. Pop each element and insert it into a helper stack, first moving larger elements from the helper back to the input stack, which keeps the helper sorted from bottom to top. No general-purpose sort may be used.

Return the sorted stack from bottom to top (smallest at the bottom).

Hint

Insertion sort using a second stack: move larger elements out of the way before placing each value.

Test cases

case 1

in: [[3,1,2]]

expected: [1,2,3]

case 2

in: [[]]

expected: []

case 3

in: [[5,4,3,2,1]]

expected: [1,2,3,4,5]

case 4

in: [[1,3,2]]

expected: [1,2,3]

Starter codePython

def sort_stack(values):
    # Your code here
    pass

4 test cases · run your code against them in the editor