Push Swap

Given a list of integers on stack A, output the shortest sequence of operations to sort them using only two stacks and a fixed instruction set. No comparison sorts, no built-ins. The fewer operations, the better.

The instruction set

The algorithm

1. Normalize the integers to their rank (0 to N-1), which removes value gaps and simplifies comparisons
2. Small inputs (2-3 elements) use hardcoded optimal sequences
3. Larger inputs push elements to stack B in ranked chunks, then pull them back to A using cost-optimized rotations

The cost model looks at how many moves each element needs to reach its correct position in both stacks at once, and always picks the cheapest next move.

Performance

Running it

./push_swap 4 67 3 87 23
 
# verify correctness
./push_swap 4 67 3 87 23 | ./checker 4 67 3 87 23
# OK
 
# count operations
./push_swap 4 67 3 87 23 | wc -l

make        # builds push_swap
make bonus  # builds the checker