package container;

public class Strings {

    /**
     * Sort an array of fixed-length strings using LSD sorting in O(WN) time
     * @param a The specific array of N strings to be sorted.
     * @param W The length of each fixed-size string.
     */
    public static void LsdSort(String[] a, int W) {
        int N = a.length;
        int R = 256;
        String[] aux = new String[N];
        // sort by key-index sorting from dth to 0th in the string
        for (int d = W - 1; d >= 0; d--) {
            int[] count = new int[R+1];
            // compute frequency counts
            for (int i = 0; i < N; i++) {
                count[a[i].charAt(d) + 1]++;
            }
            // Transform counts to indices
            for (int r = 0; r < R; r++) {
                count[r+1] += count[r];
            }
            // Distribute the records
            for (int i = 0; i < N; i++) {
                aux[count[a[i].charAt(d)]++] = a[i];
            }
            // copy back
            for (int i = 0; i < N; i++) {
                a[i] = aux[i];
            }
        }
    }
}
@@ -269,17 +269,17 @@
 ic void 
-L
+l
 sdSort(S
@@ -1064,32 +1064,32 @@
 ;%0A            %7D%0A
-
         %7D%0A    %7D%0A
@@ -1088,9 +1088,1535 @@
 %7D%0A    %7D%0A
+%0A%0A    private static String%5B%5D aux;%0A    private static int R;%0A    /**%0A     * Sort an array of strings using MSD sorting.%0A     *%0A     */%0A    public static void msdSort(String%5B%5D strs) %7B%0A        int N = strs.length;%0A        aux = new String%5BN%5D;%0A        R = 256;%0A        msdSort(strs, 0, N-1, 0);%0A    %7D%0A    /**%0A     * Sort the string array in a specific range based on dth character.%0A     */%0A    private static void msdSort(String%5B%5D a, int fromIndex, int toIndex, int d) %7B%0A        if (fromIndex %3C toIndex) %7B%0A            int%5B%5D count = new int%5BR+2%5D;%0A            // compute frequency counts%0A            for (int i = fromIndex; i %3C= toIndex; i++) %7B%0A                count%5BcharAt(a%5Bi%5D, d) + 2%5D++;%0A            %7D%0A            // transform couts into indices%0A            for (int r = 0; r %3C R+1; r++) %7B%0A                count%5Br+1%5D += count%5Br%5D;%0A            %7D%0A            // distribute%0A            for (int i = fromIndex; i %3C= toIndex; i++) %7B%0A                aux%5Bcount%5BcharAt(a%5Bi%5D, d) + 1%5D++%5D = a%5Bi%5D;%0A            %7D%0A            // copy bak%0A            for (int i = fromIndex; i %3C= toIndex ; i++) %7B%0A                a%5Bi%5D = aux%5Bi - fromIndex%5D;%0A            %7D%0A            // recursive sort for each character%0A            for (int r = 0; r %3C R; r++) %7B%0A                msdSort(a, fromIndex+count%5Br%5D, fromIndex+count%5Br+1%5D-1, d+1);%0A            %7D%0A        %7D%0A    %7D%0A    // return the ascii code of the dth character in the string, or -1 if not in.%0A    private static int charAt(String s, int d) %7B%0A        return d %3C s.length() ? (int)s.charAt(d) : -1;%0A    %7D%0A
 %7D

implement msd sort