What are the odds?

How unlikely is unlikely?

A while ago I saw a video of a sorting algorithm visualizer. It made sounds and everything! It … scratched my brain. Like an itch I did not know I had. So I decided to make my own. Make it nice, add some colors, some sounds and a bunch of different algorithms.

Implementation

I decided to go with an array of 52 numbers. 1 - 52. It just looks good. A randomized array of 52 numbers is also complex enough that it takes the algorithms some time to sort so it is fun to watch. Setting up the sorting was pretty annoying to be honest. The math for the different algorithms is available online and easy enough to make your own version of. I wrote this originally in javascript with types using jsdoc comments… then I realized I was doing types without out the niceties of typescript with worse looking code. So I ended up doing a rewrite in typescript eventually. The logic around the data from the svelte component to the algorithms and back was a bit tricky to get right.

Technically, the data flow is a simple loop. The Svelte component owns the current array (and any UI state like which indices are active), then a selected algorithm runs as a step-emitter, that yields small operations like compare(i,j), swap(i,j), or set(i,value) instead of mutating the UI directly. A scheduler (timer/requestAnimationFrame, depending on the chosen speed) consumes one step at a time, applies it to the component’s array state, and that single state update drives everything else. The bars re-render from the array values, highlights update from the step metadata, and the sound is triggered from the same step payload (e.g. using the moved value(s) or indices to pick pitch/volume). This keeps the algorithms pure … ish and makes the visualization/audio a good visual and auditory representation of what is happening.

Had some minor issues with some of the algorithms (the ones that split the array) not being correctly sorted, getting the damn bars to scale to the display width and many issues with getting the audio of the sorting process not to sound like you were torturing an alien. But after a while the project was looking pretty solid. I could now look at, and hear, algorithms sort through pillars of different heights. The marvels of the modern age never seas to amaze. Flying cars be damned.

After setting this up I was sitting and staring at my different sorting algorithms go. The amazing inefficiency of buble-sort, the mesmerizing back and forth of cocktail-sort, the structure of heap-sort and the efficiency of quick-sort, I started wondering about the maths of this.

Maths

An array of 52 items. There are 52! possible combinations … witch is a rather large number. 8.07 × 10^67, same number as a deck of cards. And as they say, if you shuffle a deck it will in all likelihood be a combination of those cards that has never been in that exact order before.

To put 52! in perspective: our solar system contains roughly 1.3 × 10^57 atoms, 52! is about 62 billion times larger than that.

Even if you shuffled a deck of cards once per second since the Big Bang, you still wouldn’t come close to going through all the permutations. The universe is about 1.38 × 10^10 years old, which equals roughly 4.35 × 10^17 seconds. That means you’d only achieve 4.35 × 10^17 shuffles—leaving you 1.85 × 10^50 times short of the 8.07 × 10^67 total permutations.

In other words, you’d need to shuffle continuously for trillions upon trillions of universe lifetimes to cover every possible permutation.

The number of combinations being so large is only when we are looking at the ods of every item being in the right place. Most of the sorting algorithms are just doing basic comparisons and swaps on items next to each other, so sorting the array does not take that long. Even bubble-sort, with no delay set, does it in around 7 seconds. Quick-sort does it in a little over 1 second. The bottleneck is the visualization and sound. This visualizer is not made for speed but for showing how the different algorithms work. And since they all run with the same array size and parameters, the speed difference should still be representative of the different algorithms.

Bogo-sort

When I was looking at the bars get sorted I switched to bogo-sort. The meme of an algorithm, shuffling the array, checking if it is sorted, if not shuffle again. Rinse and repeat until sorted. The odds of bogo-sort working with this size of an array are so insane that it is not even funny. The expected number of shuffles to sort an array of 52 items is 52! (8.07 × 10^67). If you could do a shuffle every nanosecond it would take you around 2.56 × 10^51 years to sort the array. The universe is estimated to be around 1.38 × 10^10 years old. So you would need to wait around 1.85 × 10^41 times the age of the universe to get a sorted array with bogo-sort. Or it could just work on the first try. But the odds, like I have laid out, are not in your favor.

Humans and probability

Humans are really bad at understanding probability. We tend to see patterns where there are none, we think that a coin that has landed on heads 5 times in a row is more likely to land on tails the next time (it is not, the odds are still 50/50). We also tend to underestimate the odds of very unlikely events happening. Like winning the lottery. The odds of winning the jackpot in a 6/49 lottery are around 1 in 13.98 million. Yet people buy tickets all the time, thinking they might win. The reality is that you are more likely to be struck by lightning (1 in 1.2 million depending on location ofc) than to win the lottery.

There is a known myth that if you strike your palm against a table there is a tiny, miniscule, infinitesimally small chance that the atoms in your hand will all line up wit the tables and you will phase through the table. The odds of this happening are around 1 aginst fuckalltillion. So while it is technically possible, it is so unlikely that it is basically physically impossible… but that does not stop teens around the world smacking their tables every now and again, because hey, you never know.

We love to think that odds are stupid and if there is a chance, its basically 50/50 right? Either it happens or it doesn’t.

I think it is our nature to see hope, even when the odds are against us. We want to believe that the impossible is possible, or at least that the unlikely is not really that unlikely.

I even created an intelligent bogo-sort that saves each permutation it has tried and does not try it again (reset every time you try sadly, I did not want to pay for that database table). This costs memory, I was hoping to write something that was a bit of a memory hog, but storing different permutations of 52 items does not take that much memory. I ran it for 10 minutes and it had only used around 200mb. Burns through my battery like crazy though 🤭

Maybe one day

The highest I have ever seen the intBogo-sort get is 15%. I run it every now and again, hoping to see it get a bit further. Maybe one day I will run the sort and it will instantly sort the array, one day. And on that day I will stand on a hill with a long metal rod, during a lighting storm, slapping my palm against a table, a lottery ticket in the other, screaming for all the gods to smite me down for being too powerful.

You can run the visualizer yourself here.