38
$\begingroup$

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?

$\endgroup$
  • 13
    $\begingroup$ It would be perfectly appropriate to write to him: hanyij@umkc.edu. $\endgroup$ – Joseph O'Rourke May 18 '11 at 19:04
  • $\begingroup$ Yes. We've discussed this general issue before, and the right way to address this is to email the author. $\endgroup$ – Suresh Venkat May 19 '11 at 3:12
  • 17
    $\begingroup$ 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. $\endgroup$ – Huck Bennett May 19 '11 at 4:30
  • 17
    $\begingroup$ 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. $\endgroup$ – Ari May 19 '11 at 8:23
  • 4
    $\begingroup$ 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). $\endgroup$ – Ari May 27 '11 at 8:08
18
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Why the downvote ? $\endgroup$ – Suresh Venkat Mar 17 '12 at 17:40
  • 1
    $\begingroup$ I just added this journal-article link to the Exponential tree wikipedia page. FYI: This article might of been published after the question was asked. $\endgroup$ – A T Mar 18 '12 at 6:06
  • $\begingroup$ @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. $\endgroup$ – Kaveh Mar 18 '12 at 18:15
  • 1
    $\begingroup$ 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. $\endgroup$ – Ari Jun 25 '12 at 7:13
  • 2
    $\begingroup$ 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. $\endgroup$ – Ari Jul 5 '12 at 10:17
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Ari May 22 '11 at 5:25
  • $\begingroup$ im not further reducing size, i was suggesting how to reduce size which was not required in your answer. Sorry for the confusion. $\endgroup$ – singhsumit May 24 '11 at 7:59
  • $\begingroup$ 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? $\endgroup$ – Ari May 24 '11 at 13:28
  • $\begingroup$ 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. $\endgroup$ – singhsumit May 24 '11 at 14:59
  • $\begingroup$ 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. $\endgroup$ – Ari May 25 '11 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.