RadixSort.java

import java.util.Arrays;
import java.util.List;

public class RadixSort {
	public static List<String> sort(List<String> strings, int maxDigits) {
		List<String> sorted = strings;
		for (int i = maxDigits - 1; i > 0; i--) {
			sorted = countSort(sorted, i);
		}
		return sorted;
	}

	private static List<String> countSort(List<String> words, int digitIdx) {

		int[] count = new int[128];
		for (String word : words) {
			char digit = digitIdx < word.length() ? word.charAt(digitIdx) : 0;
			count[digit]++;
		}

		for (int i = 1; i < count.length; i++) {
			count[i] = count[i] + count[i - 1];
		}
		String[] sorted = new String[words.size()];
		for (int i = words.size() - 1; i >= 0; i--) {
			String word = words.get(i);
			char digit = digitIdx < word.length() ? word.charAt(digitIdx) : 0;
			count[digit]--;
			sorted[count[digit]] = word;
		}
		return Arrays.asList(sorted);
	}

	public static void main(String[] args) {
		List<String> words = Arrays.asList("ax", "aza", "aba", "axa", "a",
				"ab", "aa");
		System.out.println(countSort(words, 1));
		System.out.println(sort(words, 3));
	}
}