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 . The number of 0s to the left of site k is . Note that if , then .

It might be interesting to track how and 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.