I can not see why MSD radix sort is theoretically as efficient as LSD radix sort

Question

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!

Answer 1

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$.