# One-dimensional Particle Physics and BubbleSort

I recently perused Donald Knuth’s website and saw that he once had a lecture called Constructing bubblesort at random: one-dimensional particle physics. As a physicist and software engineer, I naturally found this interesting. So, I thought I’d play with it.

### The code

One of the papers Knuth links to on the site for his talk gives the following instructions:

Start with infinitely many 1s followed by infinitely many 0s; then randomly interchange adjacent elements that are out of order.

The code in my Github repo is modeled after those instructions and what is in Knuth’s lecture. Basically, start with a chain of 1s and 0s, as specified below, sort them at random. It also tells you:

• How many random swaps it takes to sort the list
• The distribution of 1s and 0s (histograms), in case you want to plot them

Ok, great. But how does this relate to particle physics?

### The physics connection

The physics connection becomes a bit more clear if you imagine a 1D lattice, where the 1s are particles and the 0s are vacancies. Now, pick any site k and ask how many particles are to the right of site k. Call the result $R_k$. The number of 0s to the left of site k is $L_k$. Note that if $k=N/2$, then $R_k=L_k$.

It might be interesting to track how $R_k$ and $L_k$ change with “time”. Here, time means the number of random swaps needed to sort the list. For a long lattice, it might also be interesting to compute the distribution of 1s or 0s as a function of lattice site index. Then we could watch it change from all 1s on the left to all 1s on the right. Might look like a Heaviside Step Function inverting bit by bit.

Knuth specifically connects this toy problem to Young Tableaux, which are a way of describing the representations of certain groups (some of which are relevant to particle physics). My code doesn’t really go into any of this. I thought the things in the above paragraphs were more interesting.