[kkaranth]

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

[MaxBarraclough]

> only applies when using the traditional greater/less than comparison model

What do you mean by this?

[brmgb]

The bound is a bound on comparaison sort not a general bound on sorting.

If you don't use comparaison you can sort faster. Pigeonhole sort is linear for example.

[MaxBarraclough]

Right, comparative and non-comparative sorting algorithms.

I'd say radix sort is the canonical example of a non-comparative sorting algorithm.