<p>I was just wondering the same thing.</p>

<p>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: <strong><a href="http://www.ijcaonline.org/volume24/number3/pxc3873876.pdf">Implementation and Performance Analysis of Exponential Tree Sorting</a></strong></p>

<p>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 <strong>Han's $\bf O(n \log\log n)$ time, linear space, integer sorting algorithm</strong>:</p>

<blockquote>
  <p>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.</p>
</blockquote>

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

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

CC BY-SA 3.0
2012-03-17T17:40:43.833Z
Why the downvote ?
Suresh Venkat
CC BY-SA 3.0
2012-03-18T06:06:15.903Z
I just added this journal-article link to the [Exponential tree](http://en.wikipedia.org/wiki/Exponential_tree#See_also) wikipedia page. FYI: This article might of been published after the question was asked.
A T
CC BY-SA 3.0
2012-03-18T18:15:57.113Z
@AT, could you please expand your answer a little bit and explain how it answers the question. Right now the only thing it gives is a link to an article in some journal.
Kaveh
CC BY-SA 3.0
2012-03-19T05:35:57.190Z
Kaveh: Done and done
A T
CC BY-SA 3.0
2012-06-25T07:13:42.433Z
Well, I've already given up on Han's paper, so I'm glad you've been able to provide this help.  I didn't really expect to see anything when I came back here today.  Thanks! I'll read this new paper and see if it helps me make progress on Han's paper.
Ari
CC BY-SA 3.0
2012-07-05T10:17:50.190Z
Well, I've now read it, and I'll allow that possibly I completely misunderstood it, but barring that, there appears to be a slight problem.  The authors claim their tree has height O$(\log\log n)$, but if the tree has height $h$, then it has $(h+1)!$ leaves, and therefore less than $2\cdot(h+1)!$ nodes in total.  Let's generously assume each node holds $h+2$ keys.  Then the tree contains less than $2\cdot(h+2)!$ keys.  If $2\cdot(h+2)!=n$ then $h=\Omega(\log n/\log\log n)$.  Anyway, even if the authors are correct, they neither achieve O$(\log\log n)$ sorting, nor explain Han, so not useful.
Ari
CC BY-SA 3.0
2012-03-17T16:30:33.860Z
2012-03-19T05:35:41.107Z
2012-03-19T05:35:41.107Z
A T
<p>im not sure about the answer (haven't gone through paper) but i think this should help. The  numbers are packed into a single word, so operations on a single word take O(1) time. If there are, say, k numbers of h bits each then word size depends on k,h which in turn also depends on the range of numbers. So we use range reduction techniques that can reduce the range of numbers so that many numbers can fit in a single word. Then creating proper bit masks, we can find separate larger integers from the shorter ones considering two words at a time. This can be done in O(1) time. (Ontuition: for this each number stored in word has a flag bit associated with it and then we subtract two words... if the flag bit goes then it's smaller a number).</p>

<p>Similarly using above we can also sort any word containing k numbers in O(log k) time (bitonic sort). </p>

<p>Edit:
Algorithm to sort 2k numbers in the range 0 to m-1 packed in a word where each number takes size L of = log(m+k)+2. </p>

<p>$K_1$ be 1:000000 1:000000 1:000000 1:000000....... so on where the bit before colon is also called flag bit and each sequence is L bits long and is repeated 2k times in the word K_1.(Colon is only for understanding)</p>

<p>$K_2$ is (2k-1)(2k-2)....1 written in binary.
Sketch of algorithm:</p>

<p>Repeat for t=log k to 0. </p>

<p>Part 1 - separate the original word Z into two words A and B.</p>

<ol>
<li><p>Let T be obtained by shifting $K_2$, (L-1-t positions) to the left and ANDing the result with $K_1$. Let M=T-(T shifted L-1 places).</p></li>
<li><p>And Z with M and shift the result ($2^t L$) places to right. This gives A.</p></li>
<li><p>B=Z-(Z&amp;M).</p></li>
</ol>

<p>Part 2</p>

<ol>
<li><p>M=((A OR $K_1$)-B)&amp; $K_1$</p></li>
<li><p>M=M-(M shifted left L-1 places).</p></li>
<li><p>MIN=(B&amp;M) OR (A-(A&amp;M))</p></li>
<li><p>MAX=(A&amp;M) OR (B-(B&amp;M))</p></li>
<li><p>MAX is shifted by $2^t L$ places.</p></li>
<li><p>Finally appropriately ORing MAX and MIN we get back Z.</p></li>
</ol>

<p>I have given the sketch, hope you can fill up necessary details required.</p>

CC BY-SA 3.0
2011-05-22T05:25:05.447Z
I'm not clear on what you are suggesting.  The assumption is that the integers are already small and k of them are already packed into a single word.  Are you proposing to further reduce their size?  If so, what do you do then?  Also, I know how to sort a bitonic sequence packed into a single word in O(log k) time, or to sort a general (non-bitonic) sequence in O(log^2 k) time.  If you know an algorithm that sorts a general sequence in O(log k) time, could you please describe it in more detail?  (Such an algorithm would of course solve the selection problem.)
Ari
CC BY-SA 3.0
2011-05-24T07:59:12.780Z
im not further reducing size, i was suggesting how to reduce size which was not required in your answer. Sorry for the confusion.
singhsumit
CC BY-SA 3.0
2011-05-24T13:28:57.290Z
Unless I've misunderstood it, this looks like the algorithm for sorting bitonic sequences.  It doesn't sort general sequences.  For example, does it sort the sequence 3,0,2,0, where the 3 is in the leftmost (most significant) field?
Ari
CC BY-SA 3.0
2011-05-24T14:59:49.377Z
3 0 2 0 is separated n we get A=3 2 and B=0 0 then MAX becomes 3 2 and MIN is 0 0. Then we have new Z as 3 2 0 0. Any general sequence has bitonic sequence of size 2. with each iteration these sizes get double and finally in log k time we have our answer.
singhsumit
CC BY-SA 3.0
2011-05-25T06:30:13.437Z
No.  The numbers don't get compacted, only shifted down.  In the first iteration we split pairs of numbers differing in the high bit of their position so we get A=0 3 0 2 and B=0 0 0 0, so MIN=0 0 0 0, MAX=0 3 0 2, and Z=3 0 2 0.  In the second iteration we split pairs differing in the low bit of their position, so again we get A=0 3 0 2, B=0 0 0 0, and again Z remains unchanged.
Ari
CC BY-SA 3.0
2011-05-25T09:01:47.117Z
Yes, i remember now that this was used for merging two sorted words. Sorry for the confusion. The above will work only for bitonic and requires $O(log^2 k)$ time for any general sequence atleast as you said. i will probably go through the papers and will then comment if i get anything.
singhsumit
CC BY-SA 3.0
2011-05-25T09:26:07.280Z
i just read the second paper u referred, it clearly gives a good idea about selection with one reference to pack the numbers. so exactly what is ur problem, can u restate in short. As far as k is considered it is suitably fixed so that we get desired complexity like k=log n.
singhsumit
CC BY-SA 3.0
2011-05-26T05:54:03.123Z
My problem is that Han doesn't say what to do in the base case of his recursive selection algo.  Without the base case there is no algorithm.  The base case is $n=\text{O}(\log k)$, for which the complexity requirement is $\text{O}(\log k)$.  I can state my question independently of the broader context: given a sequence of $k$ integers packed into a single word, and a parameter $0\leq i\leq k$, find the $i$th smallest number in $\text{O}(\log k)$ time.  You can't do it by sorting+compaction because each compaction itself takes $\theta(\log k)$ time, so you're back to $\theta(\log^2 k)$.
Ari
CC BY-SA 3.0
2011-05-19T17:18:50.980Z
2011-05-24T08:02:55.277Z
2011-05-24T08:02:55.277Z
singhsumit
<p>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 (<a href="http://dx.doi.org/10.1016/j.jalgor.2003.09.001">Deterministic sorting in $O(n \log\log n)$ time and linear space</a>. 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 (<a href="http://dx.doi.org/10.1006/inco.2001.3053">Improved fast integer sorting in linear space</a>. 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.</p>

<p>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.</p>

<p>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?</p>

CC BY-SA 3.0
2011-05-18T19:04:20.547Z
It would be perfectly appropriate to write to him: hanyij@umkc.edu.
Joseph O'Rourke
CC BY-SA 3.0
2011-05-19T03:12:31.977Z
Yes. We've discussed this general issue before, and the right way to address this is to email the author.
Suresh Venkat
CC BY-SA 3.0
2011-05-19T04:30:02.940Z
This includes a specific question about a paper that's 7 years old and has already gone through the peer review process. While Ari could email the author, this seems like an ideal question for this site. I don't understand the deflection.
Huck Bennett
CC BY-SA 3.0
2011-05-19T08:23:15.920Z
Of course the first thing I did was write Han.  No answer.  Then I reached out through a contact to someone else who has done integer-sorting research, and he said that upon perusal he had found the papers to be too messy to merit further investment of his time.  That's when I came here.  If there's anyone out there who knows Han and can get his attention on my behalf, that would be great too.
Ari
CC BY-SA 3.0
2011-05-23T17:02:11.687Z
Since general sorting has lower bound $\mathcal{O}(n \log n)$, there have to be some restrictive assumptions on the inputs in place. If you have not done so yet, try to extract and understand (and maybe even edit into your question!) those. Assuming they use number of comparisons as time measure, of course.
Raphael
CC BY-SA 3.0
2011-05-27T08:08:27.480Z
General sorting does not have an $\Omega(n\log n)$ lower bound.  Quite the opposite---it is sorting restricted to comparisons that has this bound.  The issue here is not restricting the input but rather enhancing the computational model. My computational model is any of the unit cost RAM flavors, and I'll allow any reasonable assumptions (such as the availability of constants that depend on the word length).
Ari
<ds.algorithms><sorting>
Han's $O(n \log\log n)$ time, linear space, integer sorting algorithm
Ari
# Han's $O(n \log\log n)$ time, linear space, integer sorting algorithm

(Asked by: username_0 on 2011-05-18)

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](http://dx.doi.org/10.1016/j.jalgor.2003.09.001). 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](http://dx.doi.org/10.1006/inco.2001.3053). 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?

**Tags:** ds.algorithms, sorting

> **Comments:**
> **username_1**: It would be perfectly appropriate to write to him: hanyij@umkc.edu.  
> **username_2**: Yes. We've discussed this general issue before, and the right way to address this is to email the author.  
> **username_3**: This includes a specific question about a paper that's 7 years old and has already gone through the peer review process. While username_0 could email the author, this seems like an ideal question for this site. I don't understand the deflection.  
> **username_0**: Of course the first thing I did was write Han.  No answer.  Then I reached out through a contact to someone else who has done integer-sorting research, and he said that upon perusal he had found the papers to be too messy to merit further investment of his time.  That's when I came here.  If there's anyone out there who knows Han and can get his attention on my behalf, that would be great too.  
> **username_4**: Since general sorting has lower bound $\mathcal{O}(n \log n)$, there have to be some restrictive assumptions on the inputs in place. If you have not done so yet, try to extract and understand (and maybe even edit into your question!) those. Assuming they use number of comparisons as time measure, of course.  
> **username_0**: General sorting does not have an $\Omega(n\log n)$ lower bound.  Quite the opposite---it is sorting restricted to comparisons that has this bound.  The issue here is not restricting the input but rather enhancing the computational model. My computational model is any of the unit cost RAM flavors, and I'll allow any reasonable assumptions (such as the availability of constants that depend on the word length).  

---

## 2 answers

### Answer by username_5 on 2012-03-17. Score: 19

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](http://www.ijcaonline.org/volume24/number3/pxc3873876.pdf)**

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.

> **Comments:**
> **username_2**: Why the downvote ?  
> **username_5**: I just added this journal-article link to the [Exponential tree](http://en.wikipedia.org/wiki/Exponential_tree#See_also) wikipedia page. FYI: This article might of been published after the question was asked.  
> **username_6**: @AT, could you please expand your answer a little bit and explain how it answers the question. Right now the only thing it gives is a link to an article in some journal.  
> **username_5**: username_6: Done and done  
> **username_0**: Well, I've already given up on Han's paper, so I'm glad you've been able to provide this help.  I didn't really expect to see anything when I came back here today.  Thanks! I'll read this new paper and see if it helps me make progress on Han's paper.  
> **username_0**: Well, I've now read it, and I'll allow that possibly I completely misunderstood it, but barring that, there appears to be a slight problem.  The authors claim their tree has height O$(\log\log n)$, but if the tree has height $h$, then it has $(h+1)!$ leaves, and therefore less than $2\cdot(h+1)!$ nodes in total.  Let's generously assume each node holds $h+2$ keys.  Then the tree contains less than $2\cdot(h+2)!$ keys.  If $2\cdot(h+2)!=n$ then $h=\Omega(\log n/\log\log n)$.  Anyway, even if the authors are correct, they neither achieve O$(\log\log n)$ sorting, nor explain Han, so not useful.  

---

### Answer by username_7 on 2011-05-19. Score: 1

im not sure about the answer (haven't gone through paper) but i think this should help. The numbers are packed into a single word, so operations on a single word take O(1) time. If there are, say, k numbers of h bits each then word size depends on k,h which in turn also depends on the range of numbers. So we use range reduction techniques that can reduce the range of numbers so that many numbers can fit in a single word. Then creating proper bit masks, we can find separate larger integers from the shorter ones considering two words at a time. This can be done in O(1) time. (Ontuition: for this each number stored in word has a flag bit associated with it and then we subtract two words... if the flag bit goes then it's smaller a number).

Similarly using above we can also sort any word containing k numbers in O(log k) time (bitonic sort).

Edit:
Algorithm to sort 2k numbers in the range 0 to m-1 packed in a word where each number takes size L of = log(m+k)+2.

$K\_1$ be 1:000000 1:000000 1:000000 1:000000....... so on where the bit before colon is also called flag bit and each sequence is L bits long and is repeated 2k times in the word K\_1.(Colon is only for understanding)

$K\_2$ is (2k-1)(2k-2)....1 written in binary.
Sketch of algorithm:

Repeat for t=log k to 0.

Part 1 - separate the original word Z into two words A and B.

1. Let T be obtained by shifting $K\_2$, (L-1-t positions) to the left and ANDing the result with $K\_1$. Let M=T-(T shifted L-1 places).
2. And Z with M and shift the result ($2^t L$) places to right. This gives A.
3. B=Z-(Z&M).

Part 2

1. M=((A OR $K\_1$)-B)& $K\_1$
2. M=M-(M shifted left L-1 places).
3. MIN=(B&M) OR (A-(A&M))
4. MAX=(A&M) OR (B-(B&M))
5. MAX is shifted by $2^t L$ places.
6. Finally appropriately ORing MAX and MIN we get back Z.

I have given the sketch, hope you can fill up necessary details required.

> **Comments:**
> **username_0**: I'm not clear on what you are suggesting.  The assumption is that the integers are already small and k of them are already packed into a single word.  Are you proposing to further reduce their size?  If so, what do you do then?  Also, I know how to sort a bitonic sequence packed into a single word in O(log k) time, or to sort a general (non-bitonic) sequence in O(log^2 k) time.  If you know an algorithm that sorts a general sequence in O(log k) time, could you please describe it in more detail?  (Such an algorithm would of course solve the selection problem.)  
> **username_7**: im not further reducing size, i was suggesting how to reduce size which was not required in your answer. Sorry for the confusion.  
> **username_0**: Unless I've misunderstood it, this looks like the algorithm for sorting bitonic sequences.  It doesn't sort general sequences.  For example, does it sort the sequence 3,0,2,0, where the 3 is in the leftmost (most significant) field?  
> **username_7**: 3 0 2 0 is separated n we get A=3 2 and B=0 0 then MAX becomes 3 2 and MIN is 0 0. Then we have new Z as 3 2 0 0. Any general sequence has bitonic sequence of size 2. with each iteration these sizes get double and finally in log k time we have our answer.  
> **username_0**: No.  The numbers don't get compacted, only shifted down.  In the first iteration we split pairs of numbers differing in the high bit of their position so we get A=0 3 0 2 and B=0 0 0 0, so MIN=0 0 0 0, MAX=0 3 0 2, and Z=3 0 2 0.  In the second iteration we split pairs differing in the low bit of their position, so again we get A=0 3 0 2, B=0 0 0 0, and again Z remains unchanged.  
> **username_7**: Yes, i remember now that this was used for merging two sorted words. Sorry for the confusion. The above will work only for bitonic and requires $O(log^2 k)$ time for any general sequence atleast as you said. i will probably go through the papers and will then comment if i get anything.  
> **username_7**: i just read the second paper u referred, it clearly gives a good idea about selection with one reference to pack the numbers. so exactly what is ur problem, can u restate in short. As far as k is considered it is suitably fixed so that we get desired complexity like k=log n.  
> **username_0**: My problem is that Han doesn't say what to do in the base case of his recursive selection algo.  Without the base case there is no algorithm.  The base case is $n=\text{O}(\log k)$, for which the complexity requirement is $\text{O}(\log k)$.  I can state my question independently of the broader context: given a sequence of $k$ integers packed into a single word, and a parameter $0\leq i\leq k$, find the $i$th smallest number in $\text{O}(\log k)$ time.  You can't do it by sorting+compaction because each compaction itself takes $\theta(\log k)$ time, so you're back to $\theta(\log^2 k)$.  

---

