Morphogenetic Signatures in Sorting Algorithms
Cells sort themselves under perturbation, while local moves, waiting rules, and obstacles shape the order that emerges.
Can order survive when some cells stop acting?
Each cell holds a value and follows a sorting rule. Together they put themselves in order. Freeze some cells, mix different rules, or change which moves are allowed: the way order returns reveals what the collective depends on.
Order returns through temporary setbacks
In this replay, three cells cannot initiate a swap, but their neighbors can move them. Watch the error trace: the array sometimes becomes less ordered before recovering. Across 50 trials, every run contained at least one such dip.
Cells cluster when they move at different times
Algotype clustering turns out not to require attraction, type-aware communication, or explicit coordination. Temporal separation between algorithm classes is the dominant contributor. Selection cells finish early and fall quiescent. Insertion cells activate late because their sorted-prefix gate delays participation until the left portion of the array is already ordered. The mismatch produces temporally correlated swap bursts in which only one class is still rearranging, and cells active during the same burst end up adjacent. Two ablations support this reading. Removing Insertion's waiting gate (InsertionNoWait) sharply reduces clustering, and exporting the same gate to Bubble and Gnome clones reproduces the predicted rise in temporal separation and clustering. Timing differences can produce spatial pattern without an explicit instruction to group by type.
Move the waiting rule, and clustering follows
Robustness depends on operator class and obstacle semantics. Movable frozen cells can be displaced; immovable frozen indices cannot participate in swaps at all. A 2x2 factorization of 1D Selection crosses action range (adjacent vs long-range) against blocked-target policy (stubborn vs rerouting). Under immovable barriers, neither long-range reach alone nor rerouting alone survives; only the combination does. Within the published long-range Selection operator class, the rerouting ablation is decisive on its own.
Under matched immovable-index semantics, the distributed cell-view substrate does not out-perform a centralized baseline. Threaded and sequential cell-view schedules agree on which conditions succeed, with the main substrate effect appearing in compare-count work rather than in outcomes. Whatever competency the sorting cells show comes from the policy, not the distributed substrate. The policy is the rule mapping each cell's local view to its next move. The distributed architecture only matters for embodied systems that cannot run a centralized loop. In silico it is not what produces the navigation behavior.
The K-computation framework of Chis-Ciure and Levin translates the operator-and-constraint story into a graded efficiency metric. We treat the analysis as matched and exact for an explicit reachable-state proposal null, and conservative relative to blind operator-walk search. Because the state-space null is recomputed under each frozen pattern, long-range Selection's K falls as the reachable space contracts, rather than rising artificially under harder conditions. The same framework separates two failure modes: stubborn long-range Selection retains a reachable problem space but loses all successful trajectories, while adjacent operators under immovable barriers lose reachability outright in the sampled instances.
The paper PDF and TeX source live under paper/ in the repository, with every figure regenerable from committed result JSON.