3 ms·
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
by kkaranth 6y ago
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 6y ago> only applies when using the traditional greater/less than comparison model What do you mean by this?
- brmgb 6y agoThe 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 6y agoRight, comparative and non-comparative sorting algorithms. I'd say radix sort is the canonical example of a non-comparative sorting algorithm.