Complexity of LSD string sort (cfr. Algorithms by Sedgewick & Wayne)

197 views Asked by At

In Algorithms by Sedgewick & Wayne (4th edition), they state that LSD string sort uses 7WN + 3R array accesses and extra space proportional to N+R to sort N items whose keys are W-character strings taken from an R-character alphabet.

They prove this by saying: "The method is W passes of key-indexed counting, except that the aux[] arrays is initialized just once.The total is immediate from the code and PROPOSITION A."

However, 2 pages back, they state that key-indexed counting uses 11N + 4R + 1 array accesses to stably sort N items between 0 and R-1.

How is this possible? Shouldn't LSD be N+W(4R + 10N) ?

Just to be clear, I'm not looking for the big-O notation.

Thanks in advance!

Code for key-indexed counting sort (according to Algorithms):

int N = a.length;
int[] count = new int[R+1];
for (int i = 0; i < N; i++)
   count[a[i]+1]++;
for (int r = 0; r < R; r++)
   count[r+1] += count[r];
for (int i = 0; i < N; i++)
   aux[count[a[i]]++] = a[i];
for (int i = 0; i < N; i++)
   a[i] = aux[i];

Code for LSD string sort

int N = a.length;
int R = 256;
String[] aux = new String[N];
    for (int d = W-1; d >= 0; d--) 
    {

        int[] count = new int[R+1];
        for (int i = 0; i < N; i++)
            count[a[i].charAt(d) + 1]++;

        for (int r = 0; r < R; r++)
            count[r+1] += count[r];

        for (int i = 0; i < N; i++)
            aux[count[a[i].charAt(d)]++] = a[i];

        for (int i = 0; i < N; i++)
            a[i] = aux[i];
        }
    }
}
0

There are 0 answers