⏱️ Bogo Sort Estimator

Bogo Sort is the deliberately absurd sorting algorithm. Its entire strategy:

1. Shuffle the entire array randomly.
2. Check whether it happens to be in sorted order.
3. If not, go to step 1.

There is no cleverness, no divide-and-conquer, no insight of any kind. It is pure random chance applied to sorting — and it is spectacularly inefficient as a result.

Bogo Sort is not a practical algorithm. It exists entirely as a pedagogical joke, included in courses and textbooks to dramatize the difference between thoughtful algorithm design and brute-force random search.

Why it matters: After seeing Bogo Sort numbers, every other algorithm — even O(n²) Bubble Sort — looks blindingly fast by comparison. A few extra items in the array can multiply Bogo Sort’s expected runtime by millions.

The times below were measured by running Bogo Sort inside the SuperSorter app on a single machine. Multiple trials were run for each n to reduce the effect of lucky early finishes. All times are in milliseconds (ms).

The wide spread of times within each row is not measurement error — it reflects the genuine randomness of Bogo Sort. A lucky shuffle on the first or second try can produce a very short run, while an unlucky sequence can take many times the expected value. n = 7 initially had only one trial; three additional trials were later collected, bringing it to a full set of four. At n = 8+, the expected single-run time exceeds 20 minutes, making systematic data collection impractical.

Bogo Sort’s expected runtime follows directly from probability theory. Each shuffle of an n-element array produces one of n! equally likely permutations. Exactly one of those permutations is sorted, so the probability that any single shuffle produces a sorted result is 1/n!.

The number of shuffles until success follows a geometric distribution with success probability 1/n!, giving an expected value of exactly n! shuffles:

Each shuffle requires O(n) work: rearranging all n elements and then walking the full array to check whether it is sorted. Combining these two facts:

where k is a proportionality constant (in milliseconds per unit of work) that depends on the speed of the machine running the algorithm. We estimate k empirically from the collected data. For each value of n, we compute:

The k_n column in the data table above shows each of these values. Notice that they are not perfectly constant — which is expected, since each average is based on a small number of trials and Bogo Sort has very high variance. We take the mean of the k_n values as our best single estimate of k:

Important caveat: Because the runtime follows a geometric distribution, the standard deviation equals the mean. This means any individual run can easily take 2×, 5×, or even 10× the expected value — or finish in just a few lucky shuffles. All estimates below should be understood as order-of-magnitude guides, not precise predictions.

Enter any value of n to see the expected Bogo Sort runtime expressed in every time unit. The highlighted row shows the most human-readable scale for that estimate.

In this app, dots are sorted by their heights — a single numeric property. Now consider what nature must do to assemble a working protein.

Proteins are built from 20 standard amino acids — the biological equivalent of our dot “types.” Unlike sorting, where we need to find the one correct order of a given set of items, protein assembly must find exactly the right sequence of amino acids from those 20 options to produce a molecule that folds and functions correctly. Even a small protein like insulin contains 51 amino acids; a typical protein runs 200–300 or more.

The Bogo Sort analogy makes the scale of this unmistakably clear. If protein assembly worked the way Bogo Sort works — randomly shuffling 51 amino acids until the correct sequence appeared by chance — the expected waiting time would involve 51! possible arrangements. Try n = 51 in the estimator above. The result dwarfs the age of the observable universe by roughly 10⁴⁵ times.

The reason life can assemble proteins is precisely that it does not use anything like Bogo Sort. Billions of years of evolution have produced molecular machinery — ribosomes, mRNA templates, and tRNA molecules — that essentially “knows” the target sequence and builds it directly, one amino acid at a time. That is O(n) work, not O(n × n!).

The deepest lesson Bogo Sort teaches: the difference between a thoughtful strategy and the absence of one is not merely a performance detail. At biological scales, it is the difference between life itself and thermodynamic impossibility.