I absolutely loved learning about Bead Sort when I was in Uni. I was taking a class on algorithm design and Big-O notation and ended up reading through the sorting algorithms page on wikipedia[1] and then wandering off the garden path investigating a few.

There are several amusing ways that standard algorithmic analysis has been subverted with creative solutions (i.e. if you subscribe to the many-worlds theory then bogosort is always O(1) for at least one universe - you just need to discard the incorrect universes) but beadsort stood out as a really fun way to turn the problem on its head - the fact that it appears to be inspired from misusing an abacus just makes it even better.

It's a great example of why having people who can think outside of the box can be a good asset - approaching problems from unexpected directions can yield valuable and novel solutions.

1. https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o...

I'm surprised that this was only discovered in 2002. [0] Neat.

Reminds me of spaghetti sort [1], but bead sort is much cleverer.

[0] https://en.wikipedia.org/wiki/Bead_sort

[1] https://en.wikipedia.org/wiki/Spaghetti_sort

This is one of those cases where adding extraneous information confuse the illustration. It took me 2-3 times through before I figured out that color was completely irrelevant.

This needs a pause button, or at least some way to view the starting configuration. It's hard to think when everything is moving.

The optimal complexity of a sorting network of fixed width numbers is bound by depth O(log n). [1]

I'm not sure how to go about analyzing bread sort, but it does seem bound by aligning and inserting the beads into each column which would be at least O(log n), the number of digits. But, I'd be surprised if it is optimal.

[1] https://www.researchgate.net/publication/220329153_An_Optima...

Nothing better than sleep sort.

This is delightful! The actual implementation in a digital system seems to be a special case of radix sort, but it doesn't take away from the fun :)

Is it fast? I mean like, compared to QuickSort or others. Honestly asking -- I've not heard of Bead Sort before.

sorry if its offtopic but does anyone here have any experience with librarysort?

https://en.wikipedia.org/wiki/Library_sort

undefined

Go Utes! Loved the animation! Thanks for sharing.

Radix sort and counting sort are what ppl should be using.

I'm almost certain this already exists under a different name, like a columnar sort or something. Can't be bothered to Google on mobile, but this is 100000% not novel

Visual is nice though