Appendix

• Key-indexed counting

• LDS

• MSD

• Three way quick-sort.

Key-indexed counting.

• counting the frequency of each key

Initiate an array with first index blank, in our example, the key of item is a integer.

``````int N = a.length();
for(int i = 0; i < N; i++){
count[a[i].key() + 1] ++;
}
``````
• Replace count array with accumulate value

The accumulate value is the index where the item at in aux array

``````int R = count[].length;
for(int r =0; r < R; r++){
count[r+1] += count[r];
}
``````
• distribute the item to the aux array

Locate the data following the index position in count array

``````for(int i = 0; i < N; i++){
aux[count[a[i].key()]++] =a[i];
}
``````

LSD

Do index counting from right to left in a string, this method only used for sorting strings that have same length.

``````public class LSD{
public static void sort(String[] a, int W)
{  // Sort a[] on leading W characters.
int N = a.length;
int R = 256;
String[] aux = new String[N];
for (int d = W-1; d >= 0; d--)
{ // Sort by key-indexed counting on dth char.
int[] count = new int[R+1];     // Compute frequency counts.
for (int i = 0; i < N; i++)
count[a[i].charAt(d) + 1]++;
for (int r = 0; r < R; r++)     // Transform counts to indices.
count[r+1] += count[r];
for (int i = 0; i < N; i++)     // Distribute.
aux[count[a[i].charAt(d)]++] = a[i];
for (int i = 0; i < N; i++)     // Copy back.
a[i] = aux[i];
}
}
}
``````

MSD

Designed for handling the unequaled length string and optimize effectiveness of sorting small string

``````public class MSD{
private static int R = 256;// radix
private static final int M = 15;// cutoff for small subarrays
private static String[] aux;// auxiliary array for distribution

private static int charAt(String s, int d)
{
if (d < s.length()) return s.charAt(d); else return -1;
}

public static void sort(String[] a)
{
int N = a.length;
aux = new String[N];
sort(a, 0, N-1, 0);
}

private static void sort(String[] a, int lo, int hi, int d)
{  // Sort from a[lo] to a[hi], starting at the dth character.
if (hi <= lo + M)
{
Insertion.sort(a, lo, hi, d); return;
}
/*Start Doing the index counting*/
int[] count = new int[R+2];
for (int i = lo; i <= hi; i++)
// + 1 for the blanket cell in front, +1 for the -1 representation of end in tail
count[charAt(a[i], d) + 2]++;
for (int r = 0; r < R+1; r++)
count[r+1] += count[r];
for (int i = lo; i <= hi; i++)
aux[count[charAt(a[i], d) + 1]++] = a[i];
for (int i = lo; i <= hi; i++)     // Copy back.
a[i] = aux[i - lo];

for (int r = 0; r < R; r++)
//the range is between the begin of new category and the end of this new category
sort(a, lo + count[r], lo + count[r+1] - 1, d+1);
}
}
``````

Three way quick sort

``````public class Quick3String
{
private static int charAt(String s, int d)
{ if(d <s.length() return s.charAt(d); else return -1;)}

public static void sort(String[] a)
{
if(hi < lo) return;
int lt = lo, gt = hi;
int v = charAt(a[lo], d);
int i = lo + 1;
while(i <= gt)
{
int t = charAt(a[i],d);
if(t < v) exch(a, i++, lt++);
else if(t > v) exch(a, i, gt--);
else t++;
}

sort(a, lo, lt-1,d); // sort the subarray which contains items that are less than piviot
if(v > 0) sort(a, lt, gt, d+1); // sort the second letter
sort(a, gt+1,hi,d)； //sort the subarray which contains items that are larger than piviot.
}
}
``````