Han's $O(n \log\log n)$ time, linear space, integer sorting algorithm 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?
I was just wondering the same thing.

Fortunately, I was able to find a journal-article published in 2011 which explains this very thing; whats more, you don't need a subscription to view it: Implementation and Performance Analysis of Exponential Tree Sorting

I recommend reading the entire article to learn how it can be implemented and to better understand its underlying theory. It also shows how Exponential Trees stack up against Quick-Sort and Binary Trees. Here's the relevant excerpt related to Han's $\bf O(n \log\log n)$ time, linear space, integer sorting algorithm:


  Yijie Han has given an idea which reduces the complexity to expected
  time in linear space.[6] The technique used by him is coordinated pass
  down of integers on the Andersson’s exponential search tree[8] and the
  linear time multi-dividing of the bits of integers. Instead of
  inserting integer one at a time into the exponential search tree, he
  passed down all integers one level of the exponential search tree at a
  time. Such coordinated passing down provides the chance of performing
  multi-dividing in linear time and therefore speeding up the algorithm.
  This idea may provide speed up, but in practical implementation it is
  very difficult to handle integers in batches.


[6]  Y.  Han,  Deterministic  sorting  in  O(n  log  log n)  time  and linear space, 34th STOC, 2002.

[8]  A.  Andersson,  Fast deterministic  sorting  and  searching  in linear  space,  IEEE  Symposium  on  Foundations  of Computer Science, 1996.