push_swap
Sort integers with two stacks and a constrained instruction set. Includes input validation, small-stack strategies and a checker.
C · Linked lists · Cost models
The problem
Produce a valid sequence of stack instructions that sorts unique integers while keeping the operation count low.
A design decision
Handle tiny stacks separately. For larger inputs, move values to B, assign target nodes and select a low-cost reinsertion. Combine rotations when both stacks need the same direction.
A debugging edge case
After reinsertion, stack A can be ordered circularly without its minimum at the top. The final rotation aligns the minimum. Input validation also needs to reject duplicates and values outside the integer range.
A possible next iteration
A useful next iteration would expand the benchmark corpus across seeds, input patterns and boundary values, and track operation-count distributions.
Measured C operation counts
Measured on 5 October 2026 on Linux x86_64. One shuffled permutation
per size using Python Random(42). Compiled with
cc -Wall -Werror -Wextra -g; checked with the
repository’s checker.
| Integers | Operations | Checker |
|---|---|---|
| 5 | 9 | OK |
| 100 | 587 | OK |
| 500 | 4347 | OK |
These are individual samples, not average or worst-case results. Download the inputs and measurement details.
Explore the implementation
This study describes the source at commit 7238df5. The
edge case is a code walkthrough, not a personal debugging story.