push_swap — Deterministic Asymptotic Stack Sorting Engine

An algorithmic engine in pure C solving a constrained dual-stack permutation problem using a restricted 11-instruction set ($\Sigma_{11}$). Implements a tail-optimized square-root chunking strategy ($K$-Sort) minimizing operational complexity across both $100$ and $500$ element sets.

---

Algorithmic Formulation & Design

The problem requires transforming an arbitrary permutation of $N$ unique 32-bit signed integers in Stack $A$ into ascending order using an auxiliary Stack $B$ under discrete elementary operations:

$$\Sigma_{11} = { \text{sa}, \text{sb}, \text{ss}, \text{pa}, \text{pb}, \text{ra}, \text{rb}, \text{rr}, \text{rra}, \text{rrb}, \text{rrr} }$$

flowchart LR
    subgraph Phase 1: Chunk Partitioning
        A1["Unsorted Stack A"] -->|Dynamic Range Filtering| B1["Pre-Sorted Buckets in Stack B"]
    end
    subgraph Phase 2: Greedy Recomposition
        B1 -->|Min-Cost Rotation Path (rb vs rrb)| A2["Fully Sorted Stack A"]
    end

Loading

1. Indexed Normalization

Raw integer values are first transformed into continuous indices $[0, N-1]$ via an $O(N \log N)$ coordinate compression step. This decouples numerical magnitude from position calculations and allows $O(1)$ range evaluations.

2. Phase 1 — Partitioning into Stack B ($K$-Sort 1)

• Partitions Stack $A$ into dynamic sliding windows of size $W \approx \sqrt{N} \times \alpha$.
• For each element with normalized index $i$:
  • If $i \le \text{counter}$: Push to $B$ (pb) and rotate $B$ (rb) to push smaller values to the bottom.
  • If $\text{counter} < i \le \text{counter} + W$: Push to $B$ (pb) without rotation.
  • If $i > \text{counter} + W$: Rotate $A$ (ra) to evaluate adjacent elements.
• Result: Concentrates maximum elements toward the top and minimums toward the bottom of Stack $B$.

3. Phase 2 — Optimal Recomposition ($K$-Sort 2)

• Scans Stack $B$ from largest to smallest index.
• Computes minimum rotation cost vectors between forward circular shift (rb) and reverse circular shift (rrb).
• Atomically pops the maximum element back to Stack $A$ (pa) until Stack $B$ is fully depleted.

---

Performance Benchmarks

Set Size	42 5/5 Target Limit	Engine Performance	Result
3 Integers	$\le 3$ operations	$\le 2$ operations	Validated
5 Integers	$\le 12$ operations	$\le 8$ operations	Validated
100 Integers	$< 700$ operations	$\approx 590 - 640$ operations	Max Score (5/5)
500 Integers	$< 5500$ operations	$\approx 4600 - 5100$ operations	Max Score (5/5)

---

Build & Execution

Compilation

# Build optimized binary
make

# Clean object files
make clean

# Full purge
make fclean

Execution & Operation Count

# Generate random sequence and count sorting operations
ARG="4 67 3 87 23 1 90 2"
./push_swap $ARG | wc -l

# Verify sorting correctness with checker
./push_swap $ARG | ./checker_linux $ARG

---

Author & Engineering Standards

Rubén D. Higuita — Systems & Embedded Software Engineer
Madrid, Spain • LinkedIn • GitHub • Portfolio

Engineering Invariant:
Deterministic sorting complexity, optimal operation economy, zero reachable memory leaks.