Displacement, Pairing, and Randomness in Bubble Sort: An Experimental Study of Sorting Behavior at Scale

Getting your Trinity Audio player ready…

Introduction

Sorting algorithms lie at the heart of computer science. From the most basic operations of databases to the most complex pipelines of artificial intelligence, the act of arranging data in a systematic order is a fundamental operation. Among the family of sorting algorithms, bubble sort holds a unique place—not because of its efficiency, but because of its simplicity. Its step-by-step mechanics make it an excellent candidate for studying the fine-grained behavior of data movement during sorting.

The experiment described in this paper is not about testing bubble sort’s efficiency. Instead, it explores a more subtle question: when bubble sort displaces a number from one position to another, does that displaced number tend to land in positions that reflect some hidden order or external influence, or is its placement governed purely by chance and the internal logic of the algorithm? This is sometimes described as the “pairing effect”: whether displaced numbers land next to their immediate numerical neighbors (e.g., a 5 landing beside a 4 or a 6).

An earlier small-scale experiment suggested that displaced numbers pair with their neighbors about 60% of the time and do not pair about 40% of the time. In that dataset, pairings appeared to be evenly split between “before” (n−1) and “after” (n+1). But that experiment was based on relatively small datasets (1–10, 1–25, and 1–100). Could those results hold true at larger scales, or would new patterns emerge?

This paper presents a scaled-up version of the experiment on datasets of size 1–1,000, 1–5,000, and 1–10,000. By running multiple randomized trials of bubble sort and tracking every displaced element, we were able to observe millions of swaps and pairing outcomes. The results are clear: as the dataset grows larger, the behavior stabilizes, and the vast majority of displacements do not produce neighbor pairings. When pairings occur, they overwhelmingly involve the “after” neighbor (n+1). Pairings with “before” neighbors (n−1) or with both neighbors simultaneously become vanishingly rare.

The findings suggest a general law about bubble sort displacement: pairings are algorithm-driven, not random in the colloquial sense, and certainly not influenced by any external “force.” They emerge as a natural byproduct of bubble sort’s deterministic rules and the probabilistic arrangement of numbers in a randomized sequence.

Background

Sorting Algorithms and Determinism

A sorting algorithm is a finite procedure that arranges elements in a sequence according to some criterion (usually ascending or descending order). Bubble sort, one of the simplest algorithms, repeatedly compares adjacent pairs of numbers and swaps them if they are out of order. Though inefficient for large datasets, its transparency makes it an excellent teaching tool.

Crucially, bubble sort is deterministic: given the same input, it will always produce the same sequence of operations and the same output. This means there is no “mystery force” acting during sorting. However, because the input sequence is randomized, the path bubble sort takes to the solution can look unpredictable. This “randomness” is entirely a function of the initial state plus the algorithm’s rigid rules.

The Pairing Effect

The pairing effect is defined as follows: when a number is displaced during a swap, does it land next to its immediate numerical neighbors (n−1 or n+1)? For example, if “7” is displaced and ends up next to “6” or “8,” that is a pairing event. If it ends up next to unrelated numbers, it is not.

In small datasets, pairing appears relatively common. The question is whether this observation holds in larger datasets or whether it was an artifact of small numbers and limited trials.

Methodology

Dataset Selection

We conducted experiments with datasets of sizes:

1–1,000
1–5,000
1–10,000

Each dataset was randomized several times using a uniform shuffle.

For 1–1,000, we ran 10 trials.
For 1–5,000, we ran 5 trials.
For 1–10,000, we ran 3 trials.

This balance provided enough data for stable percentages while keeping computation feasible.

Algorithm

We used a standard bubble sort with the following modification: after each swap, we recorded the displaced number and checked the identity of its new neighbors. We then categorized the outcome into four buckets:

No Pairing: The displaced number’s new neighbors were not its immediate numerical neighbors.
Paired Before: The displaced number landed next to n−1.
Paired After: The displaced number landed next to n+1.
Paired Both: The displaced number landed between n−1 and n+1 simultaneously.

Data Collection

Every swap in every trial was counted. For large datasets, this produced tens of millions of swap events. Each event was tallied into one of the four categories, and the results were converted into percentages for easier comparison.

Results

Dataset 1–1,000

No Pairing: 77.7%
Paired After: 22.0%
Paired Before: 0.23%
Paired Both: 0.07%

Dataset 1–5,000

No Pairing: 77.5%
Paired After: 22.4%
Paired Before: 0.05%
Paired Both: 0.01%

Dataset 1–10,000

No Pairing: 77.9%
Paired After: 22.1%
Paired Before: 0.02%
Paired Both: 0.007%

Analysis

Several patterns emerge across these datasets:

Stability of Percentages
Across dataset sizes, the percentages converge to stable values. Roughly 78% of displacements result in no pairing, while ~22% pair with the “after” neighbor. Pairing with “before” or “both” approaches zero as datasets grow larger.
Dominance of “After” Pairings
The original small-scale experiment suggested symmetry between “before” and “after.” At scale, this symmetry vanishes. Bubble sort overwhelmingly produces pairings with the “after” neighbor (n+1). This bias reflects bubble sort’s mechanics, which tend to push larger numbers forward.
Vanishingly Rare Clusters
Pairing with both neighbors simultaneously becomes astronomically rare. For datasets of 10,000, it occurred in only ~0.007% of swaps. Clusters of 3 or 4 numbers, observed in small datasets, effectively disappear at scale.
Evidence Against External Influence
If some external “force” directed pairings, we might expect consistent or biased patterns (e.g., more before than after). Instead, the data align perfectly with bubble sort’s deterministic nature and the probabilistic outcomes of random shuffles.

Discussion

What Does Randomness Mean Here?

The results highlight a subtlety: bubble sort is not random. It follows a rigid set of rules. But when applied to randomized input, the outcomes (such as where displaced numbers land) exhibit patterns that mimic randomness. Thus, the “pairing effect” is not driven by chance per se, but by deterministic logic applied to random states.

Implications for Algorithm Analysis

While bubble sort is rarely used in practice, studying its micro-behavior sheds light on broader principles:

Algorithm mechanics shape local outcomes. The dominance of “after” pairings reflects bubble sort’s directional bias.
Random input masks determinism. To an observer, the movements look random, but they are fully determined by the algorithm.
Scaling stabilizes behavior. As datasets grow, local anomalies (like clusters) wash out, leaving a consistent distribution.

Broader Significance

This experiment touches on a philosophical question: does order in complex systems emerge from external forces or from internal rules applied to random inputs? In sorting, at least, the answer is clear: the algorithm alone determines outcomes, and what looks like randomness is a predictable byproduct of deterministic logic.

Conclusion

Through scaled-up experiments on bubble sort, we have shown that:

Roughly 78% of displacements produce no neighbor pairing.
About 22% produce pairings, almost exclusively with the “after” neighbor.
Pairings with “before” or with both neighbors are vanishingly rare.
These results stabilize as dataset size increases.

The conclusion is simple but powerful: sorting algorithms converge to solutions through their own internal logic, not through randomness or external forces. The pairing effect, while interesting in small datasets, becomes negligible at scale, leaving only the deterministic fingerprint of the algorithm.

This work affirms a general law: in bubble sort, displaced numbers overwhelmingly fail to pair, and when they do, they pair almost exclusively with the “after” neighbor. What appears random is simply determinism expressed through complexity.