Morphogenetic Signatures in Sorting Algorithms

Zhang et al. (2024) propose a minimal morphogenesis substrate. A 1D line, or 2D grid, of agents update from a local cell-view state using rules derived from classical sorting algorithms. Each cell is a thread that decides whether to swap using bounded local state and shared state protected by a lock. From those ingredients the system exhibits three behaviors: convergence to an ordered configuration in 1D, algotype clustering where cells running the same algorithm become spatially adjacent, and robustness in the presence of frozen cells.

The wrinkle is in the operator class. Bubble, Insertion, Gnome, and Shaker use adjacent swaps. Published 1D Selection performs direct transpositions toward an explicit ideal index, and reroutes when its target is blocked. Cell-view describes how each cell decides, not how it moves. The stress-tests below vary the move operator while holding that decision rule fixed.

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. The morphogenetic analogy survives, but the emphasis shifts from intelligence to heterochrony: timing shifts between developmental phases produce spatial pattern without any explicit patterning instruction.

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.