A lot of discussion on bucket/pigeon hole sorting and O(n log n), but nobody mentioning(?):
Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space, Yijie Han and Mikkel Thorup, FOCS '02 Proceedings of the 43rd Symposium on Foundations of Computer Science Pages 135-144
http://dl.acm.org/citation.cfm?id=652131
... Just thought I would throw it out there.