import java.util.Scanner;
import java.util.Arrays;

/**
 * A class to demonstrate merge sort.
 *
 * @author Mark Young (A00000000)
 */
public class MergeSort {

    /** biggest number in list */
    private static final int BIGGEST = 1000;

    /** keyboard scanner for whole program */
    private static final Scanner kbd = new Scanner(System.in);

    /**
     * Demonstrate the merge sort algorithm.
     *
     * @param args  (ignored!)
     */
    public static void main(String[] args) {
        // introduce the program
        printIntroduction();
        pause();

        // get and show original array
        int[] anArray = makeIntArray();
        System.out.println("\nArray values before sorting:");
        PrintTrace.printArray(anArray);
        pause();
    
        // sort the array
        mergeSort(anArray, 0, anArray.length);

        // show result of sorting
        System.out.println("\nArray values after sorting:");
        PrintTrace.printArray(anArray);
        pause();

        // check for a mistake in the sorting code
        if (!sorted(anArray)) {
            System.err.println("Oops!  That didn't work!");
        }
    }

    /**
     * Print an introduction to this program.
     */
    private static void printIntroduction() {
        System.out.print("\n\n"
            + "Naive Merge Sort\n"
            + "----------------\n\n"
            + "This program demonstrates using the MergeSort algorithm "
            + "in its simplest version.\n\n"
            + "Original Program: Mark Young (A00000000)");
    }

    /**
     * Create an array of random numbers.
     *
     * @return an array (size chosen by the user) of numbers in the range
     * [0, BIGGEST).
     */
    private static int[] makeIntArray() {
        // get size from user
        System.out.print("How long should I make the list? ");
        int numElts = kbd.nextInt();    
        kbd.nextLine();

        // create and return array
        int[] anArray = new int[numElts];
        for (int i = 0; i < numElts; i++) {
            anArray[i] = (int)(BIGGEST * Math.random());
        }
        return anArray;
    }

    /**
     * Sort part of an array using the merge sort algorithm,
     * showing the steps of the algorithm.
     *
     * @param arr   the array to be (partially) sorted
     * @param lo    the lower bound of the part to sort
     * @param hi    the upper bound of the part to sort
     */
    public static void mergeSort(int[] arr, int lo, int hi) {
        // calculate length of part to be sorted
        int length = hi - lo;

        // if there's more than one element to be sorted
        if (length > 1) {
            // report the range that's being sorted
            System.out.println("Sorting from " + lo + " to " + hi + "...");

            // split the range in two equal parts
            int halfLength = length / 2;
            int mid = lo + halfLength;

            // mergesort each half separately
            mergeSort(arr, lo, mid);
            mergeSort(arr, mid, hi);

            // print out the sublists before merging
            System.out.println("Merging lists:");
            PrintTrace.printArray(arr, lo, mid);
            System.out.println("and:");
            PrintTrace.printArray(arr, mid, hi);

            // merge the sublists and print out the result
            merge(arr, lo, mid, hi);
            System.out.println("Gives:");
            PrintTrace.printArray(arr, lo, hi);

            // report the range that's been sorted
            System.out.println("List sorted from " + lo + " to " + hi + ".");

            // pause to let user view the merge step
            pause();
        }
    }

    /**
     * Merge two adjacent sublists of an array.
     *
     * Preconditions:
     * <ul>
     *  <li> arr[lo..mid) is sorted in ascending order
     *  <li> arr[mid..hi) is sorted in ascending order
     * </ul>
     * Postconditions:
     * <ul>
     *  <li> arr[lo..hi) has the same elements it had before
     *  <li> arr[mid..hi) is sorted in ascending order
     * </ul>
     *
     * @param arr     the array whose parts are to be merged
     * @param lo    the beginning of the lower sublist
     * @param mid   the beginning of the upper sublist
     * @param hi    the upper bound of the upper sublist
     */
    public static void merge(int[] arr, int lo, int mid, int hi) {
        int[] firstHalf = Arrays.copyOfRange(arr, lo, mid);
        int[] lastHalf = Arrays.copyOfRange(arr, mid, hi);
        int[] result = Arrays.copyOfRange(arr, lo, hi);
        merge(result, firstHalf, lastHalf);
        for (int i = 0; i < result.length; ++i) {
            arr[lo+i] = result[i];
        }
    }

    /**
     * Merge two arrays into a third.
     *
     * Preconditions:
     * <ul>
     *  <li> onePart is sorted in ascending order
     *  <li> otherPart is sorted in ascending order
     * </ul>
     * Postconditions:
     * <ul>
     *  <li> result has the elements of onePart and otherPart combined
     *  <li> result is sorted in ascending order
     * </ul>
     *
     * @param result    the merged array
     * @param onePart   one of the arrays to be merged
     * @param otherPart the other of the arrays to be merged
     */
    public static void merge(int[] result,
                             int[] onePart,
                             int[] otherPart) {
        int i = 0;
        int j = 0;
        int k = 0;

        // merge until one list runs out
        while (j < onePart.length && k < otherPart.length) {
            if (onePart[j] < otherPart[k]) {
                result[i] = onePart[j];
                i++;
                j++;
            }
            else {
                result[i] = otherPart[k];
                i++;
                k++;
            }
        }

        // add all remaining items from onePart
        while (j < onePart.length) {
            result[i] = onePart[j];
            i++;
            j++;
        }

        // add all remaining items from otherPart
        while (k < otherPart.length) {
            result[i] = otherPart[k];
            i++;
            k++;
        }
    }

    /**
     * Wait for the user to press the enter key.
     */
    public static void pause() {
        System.out.print("\n...Press ENTER...");
        kbd.nextLine();
        System.out.println();
    }

    /**
     * Check whether the given array is sorted.
     *
     * @param arr the array to check
     * @return true if arr is sorted; false otherwise
     */
    private static boolean sorted(int[] arr) {
        for (int i = 1; i < arr.length; ++i) {
            if (arr[i - 1] > arr[i]) {
                return false;
            }
        }
        return true;
    }

}