1
$\begingroup$

Here is the pseudocode for LSD radix sort from http://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf

   public static void lsd(String[] a)
   {
        int N = a.length;
        int W = a[0].length;
        for (int d = W-1; d >=0; d--)
        {
             int[] count = new int[R];
             for(int i = 0; i < N; i++)
                   count[a[i].charAt(d) + 1]++;
             for(int k = 1; k < 256; k++)
                   count[k] += count[k-1];
             for(int i = 0; i < N; i++)
                   temp[count[a[i].charAt(d)]++] = a[i];
             for(int i = 0; i < N; i++)
                   a[i] = temp[i];
        }
   }

I guess that by 256 they mean $R$. We have a simple for loop, so the time is $\Theta(W(R+N))$ The reason why I use $\Theta$ is because the bound is tight, this is how many operations you will be doing no matter what, so it's worst case and best case performance at the same time. The space requirements are $\Theta(N+R)$

The following is the pseudocode of MSD:

    public static void msd(String[] a)
    { 
        msd(a, 0, a.length, 0); 
    }

    private static void msd(String[] a, int lo, int hi, int d)
    {
        if (hi <= lo+1) return;
        int[] count = new int[256+1];
        for (int i = 0; i < N; i++)
             count[a[i].charAt(d)+1]++;
        for (int k = 1; k < 256; k++)
             count[k] += count[k-1];
        for (int i = 0; i < N; i++)
             temp[count[a[i].charAt(d)]++] = a[i];
        for (int i = 0; i < N; i++)
             a[i] = temp[i];
        for (int i = 0; i < 255; i++)
             msd(a, l+count[i], l+count[i+1], d+1);
   }

Since the recursion we will stop recursing after $W$ levels in the worst case, the space complexity becomes $\Theta(N + WR)$

however what about time? Just from space itself, it seems like MSD is actually pretty bad. What can you say about the time? To me it looks like you will have to spend $R$ operations for every node in your recursion tree and also $N$ operations per every level. So the time is $\Theta(NW + R*amountOfNodes)$.

I do not see how and why MSD would ever be preferred in practice given these time bounds. They are pretty horrible, but I am still not sure whether I get the time bounds in a correct way, for instance I have no clue how big is amountOfNodes..

Keep in mind that I would like the analysis to be in terms of R and N. I know that in practice R is usually small so it's just a constant, but I am not interested in this scenario, since I would like to see how much does R affect the performance as well.

I asked a kind of similar question yesterday but I did receive any replies, I think the reason for that was because my question was not well structured, so I could remove this question if the admins wanted. Thank you in advance!

$\endgroup$
  • $\begingroup$ What you have here are unreadable and error-riddled samples of pseudocode. People who publish lecture notes with such nonsense should not generally be trusted to get anything else right either. $\endgroup$ – dfeuer Mar 14 '15 at 22:36
  • $\begingroup$ dfeuer I agree the pseudocode is badly written but I believe the idea of the algorithm is correct. $\endgroup$ – jsguy Mar 15 '15 at 14:54
  • $\begingroup$ I'm not sure what you mean by AmountofNodes, it should be W(R+N) just as LSD radix, since for any level there will never be more than R+N operations - the disadvantage is as you pointed out the space complexity due to recursion - the advantage is that the recursions can return early (W calls is worst case), and they can also be computed in parallel. $\endgroup$ – user3467349 Mar 21 '15 at 22:29
  • $\begingroup$ a node is just a recursive call. In each recursive call you will have to read the entire bucket array in order to find the sub problems generated by the current call, isn't that correct? When you say that in every level you will not be doing more than R+N operations, you are implying that in every level, you will just have to read the bucket array once. But this is not true, since in every level you will most likely have more than just one sub problem to work with... $\endgroup$ – jsguy Mar 22 '15 at 17:06
  • $\begingroup$ @jsguy That's correct as far as I understand the question each index of N in the bucket array is read only once per $W_i$ in total - the difference is that unlike creating a single new array from the cumulates in LSD sort, you have separate files (the total size of the sub-files is equivalent to the size of the original though). $\endgroup$ – user3467349 Mar 23 '15 at 18:29
2
$\begingroup$

If I understand OP's question correctly - the question is what is the time-complexity estimate for MSD radix sort, taking into account what OP calls AmountofNodes or recursive frames for an MSD sort, which must fill the count[] array ($R$) per each recursive frame and than iterate through the count[] array to create subfiles. I couldn't find this in the literature and I presume jsguy hasn't found a satisfactory explanation either.

I'm going to assume we are talking about the Naive MSD sort as described in the OP's pseudo code. (otherwise if you have 20 items in a subfile and $R = 256$, a hash-table would be significantly cheaper than the count[] array).

From the looks of it worst case time-complexity for that should be $\Theta(NW + NR^{(W-1)})$, where each item is unique. Specifically a worst-case number of $R$ calls will happen if none of the recursive calls terminate early (before $W_{i-1}$) and if a subfile is broken up as much as possible from the root (the maximum number of recursive calls started from any subfile is $R$).

Considering a set of subfiles $N$ - if the set is already dense duplicates only cost $W$ ($N > R^W$ and all combinations appear), if the set is sparse ($N < R^W$ and without duplicates), adding a duplicate costs at most $R(W-1)$ (if a single subfile would otherwise have terminated early at $W_1$).

If the set $N$ is sparse, either some combinations will not diverge at level $W_0$ (which is always more expensive than diverging at some further level $W_x$) or as many as possible will diverge at each level but some will terminate before $W_{i-1}$ because the branch will have only a single item remaining - therefore for sparse sets the worse-case is to have maximal divergence at each level $W$ until there are two duplicates in each subfile, for which the above estimate of $R(W-1)$ per item should apply.


edit: As to why people use MSD Radix sort, I hope someone that works with an application that utilizes Radix sort can answer that, I suspect there are cases like long RNA strings where there are very long strings with a very small $R$, and the ability to parallelize is an advantage (just a guess though). My worst case estimate definitely sounds pretty bad, but I think in practice no one tries to split a file of two duplicate items into $R$ buckets at every single $W_i$.

$\endgroup$

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.