The O(n log n) bound only holds for comparison-based sorts. It's not a matter of time; it's an assumption/precondition of the proof.
I certainly didn't realize how generalized discrimination-based sorts were. Many people I've talked to outside of the Haskell community don't know at all. I'm still working through the papers, the base of that chain is like 86 pages long!
This search fallacy has been corrected. I'm mentioning one that hasn't.
http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf
http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011c.pdf
https://www.youtube.com/watch?v=sz9ZlZIRDAg
https://hackage.haskell.org/package/discrimination
I didn't know about this until I read your reply and googled; I thought you were just obliquely referring to radix sort or something like that.I can't believe I got down voted for this thread. What does it take?
I guess I should just post it.