0
$\begingroup$

In a previous question of mine, I asked how efficient is the Least Significant Digit first radix sort algorithm for sorting 32-bit integers. It turns out that the bounds are:

Time: $ \Theta (\frac{32}{k}(n+2^k))$

Space: $\Theta (2n + 2^k)$

I have read various articles online about the efficiency of sorting the numbers by loking at the first $k$ most significant digits, applying counting sort, and recursively looking at the next $k$ digits of every new group that was just created. Most of the articles suggest that the MSD approach is actually as efficient as the LSD approach and some times even more efficient because it is more cache efficient. I tried to do the time and space analysis to see if that is the case, at least theoretically.

MSD is recursive so in every level, we have to work with $n$ elements in total because the union of all the groups of that level is going to give you the input set. However, we also have to take into account the buckets, and in this case the total amount of bucket arrays that we will need is going to be logarithmic. We know that the bucket has $2^k$ elements and now we need to find the total amount of levels. In the first level, we have a problem of size $n$, in the second level a problem of size $\frac{n}{2^k}$, in the i-th level a probem of size $\frac{n}{2^{ik}}$. When does the problem size become 1? When $\frac{n}{2^{ik}} = 1 $ so when $i = \frac{log_{2}n}{k}$.

We have $\frac{log_{2}n}{k}$ levels and in every level we need a new bucket array and the input, $\Theta(2n + 2^k \frac{log_{2}n}{k}) = \Theta(2n + 2^{k-1} \log_{2}n)$. We have $2n$ because during the counting phase we need that extra temporary array.

Now what about the time? The problem with the time is that for every sub problem generated, we will have to scan through the entire bucket array to find the next sub problems!

In every level however, we will only have to spend $\Theta(n)$ time for reading stuff and writing from/to the input. However I am really stuck at this point.

In the first level, we have one problem, in the second level $2^k$ problems.. so in total we have

$\sum_{i=1}^{\frac{\log_{2}n}{k}}2^{ik}$ sub problems?? So the time is:

$\Theta(2n + 2^k\sum_{i=1}^{\frac{\log_{2}n}{k}}2^{ik})$

This looks very bad compared to LSD radix sort... Am I doing something wrong here?

$\endgroup$
  • $\begingroup$ Obligatory $\Theta$-police comment: since $32$ is a constant and $k \leq 32$, all you have there is $\Theta(n)$ for both algorithms. So if you want to observe actual differences, you'll have to get rid of that $\Theta$ and look more closely. $\endgroup$ – Raphael Mar 11 '15 at 18:38
  • $\begingroup$ you are right that k is constant so it can be removed, but I would really want to see an analysis in terms of both n and k. $\endgroup$ – jsguy Mar 11 '15 at 18:42
  • $\begingroup$ I understand that. In that case, you need to do away with $\Theta$, as I said. You say, "oh noes, there's an extra $2^k$ term!" but the other $\Theta$ may hide an extra factor $2^{64}$. Mathematically speaking, of course. You need more rigorous analysis here. Maybe our reference question can be of help. $\endgroup$ – Raphael Mar 11 '15 at 18:46
  • $\begingroup$ My analysis was actually wrong in the way that I did it. The number of levels is going to be $32/k$ so there might be an extra constant term in that case.. but I tried and can not figure out how to find the exact form as the one in LSD. the total amount of times that we will have to read the bucket array, is going to be $\sum_{i=1}^{32/k} 2^{ik}$ which according to wolfram alpha is $\frac{2^{32}*2^k}{2^k-1}$, so the time complexity becomes $\Theta(\frac{32}{k}2n + \frac{2^{32}*2^k}{2^k-1})$ $\endgroup$ – jsguy Mar 11 '15 at 19:09
  • $\begingroup$ after thinking a little bit more, I realized that I am actually looking at the very worst case scenario... I am really stuck at the moment. Why is MSD performing as good as LSD in theory? $\endgroup$ – jsguy Mar 11 '15 at 19:48

Your Answer

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

Browse other questions tagged or ask your own question.