import java.io.*;
import java.util.*;

public class RadixSort {

	private static ArrayList<LinkedList<String>> list = new ArrayList<LinkedList<String>>(27);
	private static ArrayList<String> unsorted = new ArrayList<String>();
	private static Scanner sc;

	public static void sort(String filename) {
		init(filename);

// 		System.out.println(unsorted);
	    for(int i=0; i<unsorted.size(); i++){
	        System.out.println(unsorted.get(i));
	    }
	    //writeFile(filename);
	}



	private static void writeFile(String str) {

	    //System.out.println(unsorted.size());
	    //System.out.println(unsorted);
	    try{
            File key = new File("answer.txt");
            PrintWriter sortWrite = new PrintWriter(key);
            sortWrite.println(str);
            sortWrite.close();
            System.out.println("Created File!");
	    }catch(Exception e){
	        System.out.println(e);
	        System.out.println("Error 1");
	    }
	}

	private static void init(String filename) {
		try {
			File file = new File(filename);
			sc = new Scanner(file);
		} catch (Exception e) {
			// TODO Auto-generated catch block
			System.out.println(e);
	        System.out.println("Error 2");
		}
		list.clear();

		initList();

		int maxLength = 0;
		while (sc.hasNext()) {
			String str = sc.next();
			if (str.length() > maxLength)
				maxLength = str.length();
		}

		try {
			File file = new File(filename);
			sc = new Scanner(file);
		} catch (Exception e) {
			// TODO Auto-generated catch block
			System.out.println(e);
	        System.out.println("Error 3");
		}

		while (sc.hasNextLine()) {
			String str = sc.nextLine();
			unsorted.add(str);
		}
// 		System.out.println(unsorted.size());
	   // System.out.println(unsorted);
		sortHelper(maxLength);
	}

	private static void sortHelper(int maxLength) {
		int index = maxLength - 1;
		while (index >= 0) {
			for (String input : unsorted) {
				String temp = formatString(input, maxLength);
				list.get(hashChar(temp.charAt(index))).add(input);
			}
			reAddToUnsorted();
			index--;
		}
	}

	private static String formatString(String input, int maxLength) {
		String str = input;
		if (str.length() < maxLength) {
			for (int i = str.length(); i < maxLength; i++) {
				str = str + " ";
			}
		}
		return str.toLowerCase();
	}

	private static void initList() {
		for (int i = 0; i < 27; i++) {
			list.add(new LinkedList<String>());
		}
	}

	private static void reAddToUnsorted() {
		unsorted.clear();
		for (LinkedList<String> linked : list) {
			for (String str : linked) {
				unsorted.add(str);
			}
			linked.clear();
		}
	}

	private static int hashChar(char c) {
		int ascii = (int) c;

		if (c == ' ')
			return 0;

		return ascii - 96;
	}
}