I'm taking a graduate algorithms class right now, and stumbled upon the bead sort wiki page.
These methods are quite interesting! The bound of O(n log n) only applies when using the traditional greater/less than comparison model
These methods are quite interesting! The bound of O(n log n) only applies when using the traditional greater/less than comparison model
What do you mean by this?
If you don't use comparaison you can sort faster. Pigeonhole sort is linear for example.
I'd say radix sort is the canonical example of a non-comparative sorting algorithm.