3 ms·
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 S
by joakleaf 10y ago
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 http://dl.acm.org/citation.cfm?id=652131
... Just thought I would throw it out there.
- sangupta 10y agoThanks a bunch. I mentioned similarities to bucket sort earlier in the day. I will go over the mentioned paper and also mention it as a reference.