/**
 * Take a list of numbers from file, insert them into an array and sort them.
 *
 * @author Ulizio
 * @version 2.5
 */
import java.util.*;
import java.io.*;
import java.util.Scanner;

public class mergeSort {
    public static void main(String [] args) {

        try {
            /*
            * Read file, find amount of numbers, and scan contents into array
            */

            Scanner file = new Scanner(new BufferedReader(new FileReader("nums.txt")));

            int i = 0;

            while(file.hasNextLine()) {
               file.nextInt();
               i++;
            }

            file.close();

            Scanner file2 = new Scanner(new BufferedReader(new FileReader("nums.txt")));
            List<Integer> nums = new ArrayList<Integer>();


            for (int x = 0; x < i; x++) {

                nums.add(file2.nextInt());

            }

            /*
             * Converting arraylist to an array so that I can work with
             * fixed boundaries
             */
            int length = nums.size();
            int [] nums2 = new int [length];
            for(int z = 0; z < length; z++) {
                nums2[z] = nums.get(z);
            }

            file2.close();

            for(int x = 0; x < nums2.length; x++) {
                System.out.println(nums2[x]);
            }

            //Begin mergesort
            sort(nums2, 0, nums2.length - 1);

        }
        catch (Exception e) {

            System.out.println("YEET" + e);
        }



    }

    private static void sort(int[] sortArray, int leftBound, int rightBound) {
        /*
         * Method to sort numbers, will be called recursively.
         * Takes 3 arguments:
         * The array of numbers
         * "leftBound" or the beginning of the array
         * "rightBound" or the end of the array
         */

        int center = 0;

        if (leftBound < rightBound) {
            /*
             * If the array is not a single number, more sorty
             */

            center = (leftBound + rightBound) / 2;

            //First Half
            sort(sortArray, leftBound, center);
            //Second Half
            sort(sortArray, leftBound, center);

            /*
             * On the way back up, splice back together and print
             */

            merge(sortArray, rightBound, leftBound, center);

        }
    }

    private static void merge(int [] nums, int rightOrig, int leftOrig, int centerOrig) {
        /*
         * Takes 4 Arguments:
         * The array
         * rightBound - end of array
         * leftBound - beginning of array
         * center - center of array
         */

        //Initialize array for merging
        int sortedNums[] = new int[nums.length];
        int position = 0;

        /*
         * Temp vars to play with
         */
        int left = leftOrig;
        int right = rightOrig;
        int center = centerOrig;

        /*
         * While loops self explanatory, read like sentences
         */
        while (left <= center && center <= right) {
            //Compare values
            if(nums[left] <= nums[right]) {
                //add relevant number to final array, increment vars to continue working
                //through array.
                sortedNums[position] = nums[left];
                position++;
                left++;
            }
            else {
                sortedNums[position] = nums[center];
                position++;
                center++;
            }
        }

        while (left <= center) {
            //add relevant number to final array, increment vars to continue working
            //through array.
            sortedNums[position] = nums[left];
            position++;
            left++;
        }

        while (center <= right) {
            //add relevant number to final array, increment vars to continue working
            //through array.
            sortedNums[position] = nums[center];
        }

        //Finalize array by transferring sorted numbers
        for(int y = 0; y <= rightOrig; y++) {
            nums[y] = sortedNums[y];
        }

        //print result
        for(int x = 0; x < nums.length; x++) {
            System.out.println(nums[x]);
        }
    }
}