Implementing LSD radix sort

Question

I would love a code review of this LSD radix sort implementation. I've rolled my own, and have implemented counting sort as well. I feel like some of the data structures I've chosen could be improved. My List<List<char[]>>, for instance, is a little gross and makes fiddling with its innards more complex than I think needs to be.

public class LSDSorting {

private static final int DIGIT_RANGE = 5;


public static void main(String[] args) {
    char[][] toSort = new char[][]{"0123".toCharArray(), "1233".toCharArray(), "1212".toCharArray(), "1111".toCharArray(), "4444".toCharArray()};

    int LSD_INDEX = toSort[0].length - 1;
    char[][] sorted = lsdSort(toSort, LSD_INDEX);

    for (char[] str: sorted) {
        System.out.println(String.valueOf(str));
    }
}

private static char[][] lsdSort(char[][] toSort, int d) {
    if (d < 0) {
        return toSort;
    }

    char[][] sortedOnD = runCountingSort(d, toSort, DIGIT_RANGE);
    return lsdSort(sortedOnD, d-1);
}


private static char[][] runCountingSort(int d, char[][] toSort, int range) {
    List<List<char[]>> idx = new ArrayList<>();
    for (int i = 0; i < range; i++) {
        idx.add(i, new ArrayList<char[]>());
    }

    for (int i = 0; i < toSort.length; i++) {
        int currVal = Character.getNumericValue(toSort[i][d]);
        List<char[]> currList = idx.get(currVal);
        if (currList == null) {
            currList = new ArrayList<>();
            idx.add(currVal, currList);
        }
        currList.add(toSort[i]);
    }

    char[][] result = new char[toSort.length][toSort[0].length];
    int currIdx = 0;
    for (int i = 0; i < idx.size(); i++) {
        for (char[] str : idx.get(i)) {
            result[currIdx] = str;
            currIdx++;
        }
    }
    return result;
}
}

Answer 1

An important thing about sorting is that it has to be fast and that it does not fill your entire heap space. That's why quicksort often is prefered before merge sort.

And I think that your code is eating way more memory than it should.

• You don't need the recursion in lsdSort, I think it makes it more complex and less efficient. You may get unexpected stackoverflow exceptions as well for long strings.
• At each iteration you are creating new instances for everything you need. The char matrix and your list of lists. You may reuse the same copies each iteration if you throw away the recursion.
• Don't use List or any implementation of it when you exactly know the size and you aren't interacting with any other methods. (as you probably may know there is an overhead)
• List<char[]> currList = idx.get(currVal); followed by a nullcheck seems to make no sense for your code? List<E>.get()

How would I do it: The best implementation I've seen so far is from a book of Robert Sedgewick.

/**  
 * Rearranges the array of W-character strings in ascending order.
 *
 * @param a the array to be sorted
 * @param W the number of characters per string
 */
public static void sort(String[] a, int W) {
    int N = a.length;
    int R = 256;   // extend ASCII alphabet size
    String[] aux = new String[N];

    for (int d = W-1; d >= 0; d--) {
        // sort by key-indexed counting on dth character

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

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

        // move data
        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];
    }
}

I think your idea with using a list of lists is good. And may looks faster since you are iterating one time less by skipping the cumulated counts. Still, it's clean and simple.

LSD.java