import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static ArrayList<Integer> FileArray = new ArrayList<>();
    public static String filename = "million.txt";
    public static int counter = 10000;

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        readFile(filename);

        for (int i = 0; i < counter; i++) {
            int arrSize = FileArray.size() - 1;
            int l = i;
            int r = arrSize - i;

            quickSort(FileArray, l, r);
            System.out.println(FileArray.get(i));
        }
        long endTime = System.nanoTime();
        long durationMilli = (endTime - startTime) / 1000000;
        System.out.println("");
        System.out.println("Time elapsed "+ durationMilli + " milliseconds");

    }

    public static void readFile(String filename) {
        java.io.FileInputStream inFile = null;
        try {
            inFile = new java.io.FileInputStream(filename);
            Scanner sc = new Scanner(inFile);

            for (int i = 0; i < counter; i++) {
                FileArray.add(sc.nextInt());
                //System.out.println(FileArray.get(i));
            }

            inFile.close();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    static int partition(ArrayList<Integer> arr, int left, int right) {
        int i = left, j = right;
        int tmp;
        int pivot = arr.get((left + right) / 2);

        while (i <= j) {
            while (arr.get(i) < pivot)
                i++;
            while (arr.get(j) > pivot)
                j--;
            if (i <= j) {
                tmp = arr.get(i);
                arr.set(i, arr.get(j));
                arr.set(j, tmp);
                i++;
                j--;
            }
        }

        return i;
    }


    static void quickSort(ArrayList<Integer> arr, int left, int right) {
        int index = partition(arr, left, right);
        if (left < index - 1)
            quickSort(arr, left, index - 1);
        if (index < right)
            quickSort(arr, index, right);

    }


}