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.<p>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.<p>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.<p>1. <a href="https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms" rel="nofollow">https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_o...</a>
I'm surprised that this was only discovered in 2002. [0] Neat.<p>Reminds me of <i>spaghetti sort</i> [1], but bead sort is much cleverer.<p>[0] <a href="https://en.wikipedia.org/wiki/Bead_sort" rel="nofollow">https://en.wikipedia.org/wiki/Bead_sort</a><p>[1] <a href="https://en.wikipedia.org/wiki/Spaghetti_sort" rel="nofollow">https://en.wikipedia.org/wiki/Spaghetti_sort</a>
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.
The optimal complexity of a sorting network of fixed width numbers is bound by depth O(log n). [1]<p>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.<p>[1] <a href="https://www.researchgate.net/publication/220329153_An_Optimal_Hardware-Algorithm_for_Sorting_Using_a_Fixed-Size_Parallel_Sorting_Device" rel="nofollow">https://www.researchgate.net/publication/220329153_An_Optima...</a>
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 :)
sorry if its offtopic but does anyone here have any experience with librarysort?<p><a href="https://en.wikipedia.org/wiki/Library_sort" rel="nofollow">https://en.wikipedia.org/wiki/Library_sort</a>
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<p>Visual is nice though