import java.util.*;
import java.io.*;
class TesteSort
{

	static Vector lista = new Vector();
	public static void main(String[] args) {
		System.out.println(new Date().getTime());
		try	{
			BufferedReader b = new BufferedReader(new FileReader(args[0]));

			try	{
				while (b.ready()) {
					lista.add(b.readLine());
				}
			} catch (IOException f) {f.printStackTrace();}


		} catch (FileNotFoundException f) {
				f.printStackTrace();
				System.exit(0);}

		System.out.println(new Date().getTime());



		classifica(0, lista.size());




		System.out.println(new Date().getTime());

		try	{
			BufferedWriter b = new BufferedWriter(new FileWriter("saida"));

			try	{
				for (Iterator i = lista.iterator(); i.hasNext() ;) {
					b.write((String)i.next());
					b.newLine();
				}
			} catch (IOException f) {f.printStackTrace();}

			b.close();

		} catch (IOException f) {f.printStackTrace();}
		System.out.println(new Date().getTime());

	}

	static void classifica(int _inicio, int _numeroElementos) {
		if (_numeroElementos == 1) return;

		int indexParte1 = _inicio;
		int elementosParte1 = _numeroElementos / 2;
		int fimParte1 = indexParte1 + elementosParte1;

		int indexParte2 = _inicio + elementosParte1;
		int elementosParte2 = _numeroElementos - elementosParte1;
		int fimParte2 = indexParte2 + elementosParte2;

		classifica(indexParte1, elementosParte1);
		classifica(indexParte2, elementosParte2);
		Vector listaAuxiliar = new Vector(_numeroElementos);

		while (true) {
			if (indexParte1 == fimParte1) {
				for ( ;indexParte2 < fimParte2 ;indexParte2++ ) {
					listaAuxiliar.add(lista.get(indexParte2));
				}
				break;;
			}

			if (indexParte2 == fimParte2) {
				for ( ;indexParte1 < fimParte1 ;indexParte1++ ) {
					listaAuxiliar.add(lista.get(indexParte1));
				}
				break;;
			}

			int comparador = ((String)lista.get(indexParte1)).compareTo((String)lista.get(indexParte2));

			if	(comparador == 0) {
					listaAuxiliar.add(lista.get(indexParte1));
					listaAuxiliar.add(lista.get(indexParte2));
					indexParte1++;
					indexParte2++;
			}
			else
				if	(comparador > 0) {
						listaAuxiliar.add(lista.get(indexParte2));
						indexParte2++;
				}
				else {
						listaAuxiliar.add(lista.get(indexParte1));
						indexParte1++;
				}
		}

		for (Iterator i = listaAuxiliar.iterator(); i.hasNext(); _inicio++) {
			lista.set(_inicio, i.next());
		}
	}
}