in this project i implemented an optimized sorting algorithm as part of the StackSort project, focused on sorting a stack of integers using a limited set of operations (push, swap, rotate, and reverse rotate). The challenge was to create a highly efficient solution with minimal operations, while ensuring accuracy and optimal time complexity. This project sharpened my understanding of sorting algorithms, data structures (stacks), and algorithmic efficiency. I applied advanced techniques such as quicksort and mergesort principles, along with in-depth performance analysis, to achieve optimal results within project constraints.

How sort_stack works

1. Rank everything. The input is copied and the copy is sorted, so each number knows its rank.
2. A → B in chunks. A sliding window of ranks (about 10 wide up to 199 numbers, 33 wide above) decides each move: a number inside the window is pushed to B (pb), a number below it is pushed and sent to B's bottom (pb + rb), anything else rotates A (ra). B ends up funnel-shaped: small numbers at both ends, big ones in the middle.
3. B → A, largest first. Find the biggest number left in B. On top: pa. Second: sb pa. At the bottom: rrb pa. Otherwise rotate B the short way. A fills up already sorted.

Small inputs skip this: 2–3 numbers are solved case by case, and 4–20 numbers move the minimum to B one at a time, sort the last three, then push everything back.

Run it

make                                # builds push_swap
./push_swap 5 2 9 1 7
ARG=$(shuf -i 1-1000 -n 100 | tr '\n' ' ')
./push_swap $ARG | wc -l            # how many moves
make bonus                          # builds checker
./push_swap $ARG | ./checker $ARG   # OK or KO

_{Diagrams in docs/ are generated SVGs, drawn to match the code in this repo.}