TIL: How Fast is Solar Bitflip Sort?

Solar Bitflip Sort is a joke sorting algorithm that relies on cosmic particles colliding with transistors in a memory node to randomly flip an array of bits into a miraculously sorted arrangement. But how long would it actually take to sort an array?

A 1996 study by IBM found that their machines experienced about 1 bit flip per 256 MB of RAM per month, or $5.5 * 10^{-9}$ flips per bit per year. To calculate sorting time, we just need to figure out how many random flips it should take to sort a given array of bits.

The Theory

If we consider two arrays of $n$ bits $A$ and $B$, the difference between the current and sorted states is just the number of mismatched bits $d$, i.e. the bitwise XOR or Hamming distance. Each random flip can increase or decrease $d$ by 1, with the probability determined by the number of currently sorted bits. Since each bit theoretically has the same chance of being flipped, the probability of reducing distance by 1 is just the proportion of unsorted bits $d/n$, while the probability of increasing distance is the inverse $(n - d)/n$.

We can think of this as estimating the hitting time of a random walk in Hamming space, which should be solvable with Markov chains. Let’s just look up some equations and…

Let’s do a simulation instead!

The Simulation

To come up with an empirical estimate of required flips, we just need a function that iteratively flips the bits of a random initial state until it reaches a sorted target state. To keep things fast, I wrote this up in Rust.

use rand::{rngs::ThreadRng, Rng};

/// Flip a random bit in a vector in-place
fn flip_random_bit(state: &mut[u8], rng: &mut ThreadRng) {
    let idx = rng.random_range(0..state.len());
    state[idx] ^= 1;
}

/// Simulate the number of random flips needed to sort `n` bits once from a random state
fn count_flips_until_sorted(n_bits: usize) -> usize {
    let rng = &mut rand::rng();

    // Initialize random start and target states
    let mut state: Vec<u8> = (0..n_bits).map(|_| rng.random_range(0..=1)).collect();
    let target: Vec<u8> = (0..n_bits).map(|_| rng.random_range(0..=1)).collect();

    // Avoid starting with a sorted state
    if state == target {
        flip_random_bit(&mut state, rng);
    }

    // Flip bits until the state matches the target
    let mut flips = 0;
    while state != target {
        flip_random_bit(&mut state, rng);
        flips += 1;
    }

    flips
}

Running that function 10 million times with an array of 8 bits gives us a sorted byte after an average of 302 flips¹. How long will it take to flip those 302 bits? Based on the IBM numbers with 8 bits of data, we can expect $4.4 * 10^{-8}$ flips per year, giving us an average sorting time of 6.8 billion years. With the current age of the universe estimated at 13.8 billion years, that’s doable!