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];
}
}
}