import java.util.ArrayList;

// Written by Andrew Repine
public class RadixSort {
	
	public static void main(String[] args) {
		ArrayList<String> a = new ArrayList<>();
		a.add("The");
		a.add("juMped");
		a.add("quick");
		a.add("brown");
		a.add("fox");
		a.add("jumped");
		a.add("over");
		a.add("the");
		a.add("lazy");
		a.add("hound");
		stringRadixSort(a);
		for (String s: a) {
			System.out.println(s);
		}
		
		
	}
	
	public static void stringRadixSort (ArrayList<String> a) {
		ArrayList<ArrayList<String>> buckets = new ArrayList<>();
		for (int i = 0; i < 53; i++) {
			buckets.add(new ArrayList<String>());
		}
		int maxLength = -1;
		for (String s: a) {
			int length = s.length();
			if (length > maxLength) maxLength = length;
		}
		int i = maxLength-1;
		while (i > -1) {
			for (String s: a) {
				if (s.length()-1 < i) {
					buckets.get(0).add(s);
				} else {
					int c = s.charAt(i);
					if(c > 90) {
						c -= 65;
						c -= 32;
						c = c*2;
					} else {
						c-= 65;
						c = c*2 + 1;
					}
					if (c < 0 || c > 52) {
						throw new IllegalArgumentException("String contains characters other than A-Z or a-z");
					}
					c++;
					
					buckets.get(c).add(s);
				}
			}
			int k = 0;
			for (ArrayList<String> as : buckets) {
				for (String s : as) {
					a.set(k, s);
					k++;
				}
				as.clear();
			}
			i--;
		}
	}

}