Is anyone familiar with Yijie Han's $O(n \log\log n)$, linear space, integer sorting algorithm? This result appears in a fairly short paper (Deterministic sorting in $O(n \log\log n)$ time and linear space. J. Alg. 50:96–105, 2004) which basically glues together a lot of earlier results, with suitable adaptations. My problem is that it's written in a rather hand-wavingly manner without going very deep into any specifics. It relies heavily on previous papers, prominent among them another paper by Han (Improved fast integer sorting in linear space. Information and Computation 170(1):81–94) written in much the same style. I am having significant difficulties in understanding these two papers, particularly the way in which they adapt and use previous results. I would appreciate any help.
This is of course too broad and vague to be considered a proper question, but I am hoping to develop a discussion across several focused well defined questions and answers.
To lead off, here is my first specific question. In Lemma 2 of the Info. Comp. paper there is a recursive $O(n/k \log k)$ time algorithm for finding the mth smallest integer in a set of $n$ small integers packed $k$ each into RAM words. The description of the algorithm fails to mention how the base case $k=O(n)$ is handled. In this case it is required to do the selection in $O(\log k)$ time. How can this be done?