Self-sorting arrays
Like cells gather because of when each rule moves, not how it swaps. Frozen cells show which rules still reach order.
What can an array of sorting cells express besides order?
Each cell in the array holds a value and runs its own sorting rule, and their local swaps bring the whole array into order. When two rules share an array, cells of the same rule gather into runs along the way, and the gathering follows when each rule moves: give another rule Insertion's wait and it clusters as much as Insertion does.
Cells that wait their turn form islands in self-sorting arrays
Cells of one sorting rule gather into islands because they wait for nearby cells to sort; islands outlast the sort when one kind keeps overtaking its equals.
Cells cluster when they move at different times
The highest point of a noisy clustering curve sits above the random-mixing level even when both halves of the array run the same rule, so we score each run against its own sequence of arrangements with the type labels shuffled across cells, and report the excess over that null. Pairs that contain Insertion cluster above it. Insertion's wait holds each of its cells back until everything to its left is in order, so the late bursts of swaps involve mostly Insertion cells, and those cells end up next to each other without attraction, type-aware signals or any coordination. Zhang and colleagues suggested that cells running the more efficient rule settle first and the others catch up, but the timing comes from the wait and not from how much work a rule does. Removing the wait from Insertion returns clustering to the null, where mixtures of neighbor-swapping rules that never wait, such as Bubble and Gnome, also sit. Bubble mixed with Selection clusters by another route: with almost no difference in timing it reaches +0.073 over the null at 100 cells, because Selection cells claim the left end of the row first and gather there as a front.
The paired replay below starts from the same array with and without the wait, so the two runs differ only in when the second type is allowed to move.
Move the waiting rule, and clustering follows
We gave clones of Bubble and Gnome Insertion's wait and left their swap rules unchanged, which separates the wait from the rest of the rule. Across 30 trials per pair the delayed clones cluster as far above the null as native Insertion does (+0.064 and +0.052 against +0.061), while the same clones without the wait sit at the null, as Insertion does without its wait. A permutation test clears the 1-in-20 level in only 6 of 30 single runs of each waiting pair, so the transfer shows in the average over many runs and mostly not in any one run. The wait does not need to see far: a cell that waits only for the nearest dozen cells to its left to be in order clusters as strongly as one that waits for the whole prefix.
Getting past a cell that cannot move
A frozen cell never starts a swap. When its neighbors cannot move it either, the rules alone decide which sorts can finish. Neighbor-swapping rules cannot carry a value across a frozen cell, so they stop with each segment sorted, and a long-range Selection cell that keeps pointing at a frozen target waits forever. Of four Selection variants that cross long-range or neighbor-only swaps with rerouting or waiting at a frozen target, only long-range rerouting reaches the sorted state. Traditional sorts given the same skip-the-frozen-cell rerouting agree with the cell versions in every paired trial, so the cell-view advantage in the original comparison most likely came from traditional baselines without that rerouting, and the ability worth studying is the rerouting rule itself.
Every cell thread waits on one shared lock, so the threaded implementation is a random scheduler that runs one cell at a time. With frozen cells running no thread, as in the original code, threaded and sequential schedules of the same cells reach the same outcomes with the same work (ratios between 0.97 and 1.02). Without the lock, in a simulation where cells act on stale views of their neighbours and writes can collide, long-range rerouting still sorts past frozen cells, at about twice the writes, while the other variants still fail.
In the replay below three cells cannot start 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. We have not yet compared these dips with a random walk at the same number of swaps, or tested whether they become more frequent as more cells are frozen, which is how Zhang and colleagues argue that they are more than noise.
The K-computation framework of Chis-Ciure and Levin gives a worked example with explicit operators, constraints and costs. Our reachable-state proposal null makes K depend mostly on the size of the reachable state space. For long-range rerouting K sits 1.7 to 2.0 units below the base-10 logarithm of the number of arrangements of the active cells at every frozen count, and about 2.6 below it for the neighbor-only variants without frozen cells, so its decline with frozen count and the failure modes it separates restate the reachability result.
The full write-up, Cells that wait their turn form islands in self-sorting arrays, repeats the original duplicate-value experiment at 100 cells, where clustering outlasts the sort only when one kind of cell keeps overtaking cells of equal value in one direction. That needs no efficient rule: Insertion with a neighbor-only Selection takes 3,912 swaps per run against 1,187 with the original Selection and leaves larger lasting islands. The write-up traces every number to its result file. We have not yet revisited the opposite-direction chimeras, the three-type mixture, the comparison of cell-based with traditional sorting, or the rise of dips with frozen count.