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
        System.out.println("\n\n"
                + "Merge Sort\n"
                + "==========\n\n"
                + "This program counts how many operations it takes "
                + "for merge sort to sort a\nreversed array "
                + "of various sizes, "
                + "and compares that result to the expected value\n"
                + "of 5N log(N) / 2.");

        int len = 0;
        do {
            System.out.println();
            System.out.printf("%10s %10s %10s%n", 
                    "Length", "Operations", "Expected");
            for (int i = 1; i <= 10; ++i) {
                // create an array of random integers
                ++len;
                int[] numbers = makeReversedArray(len);

                // sort it
                int result = mergeSort(numbers, 0, len);

                // report operation count
                System.out.printf("%10d %10d %10d%n", 
                        len, result, expected(len));
            }
        } while (userContinue());
    }

    /**
     * Make an array of the given length, with the numbers 1 .. {@code length}
     * in reverse order. This is the worst case for sorting for many methods.
     *
     * @param length the length of the array to create
     * @return an array containing the numbers from {@code length} down to 1
     */
    private static int[] makeReversedArray(int length) {
        int[] result = new int[length];
        for (int i = 0; i < length; ++i) {
            result[i] = length - i;
        }
        return result;
    }

    /**
     * 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 int mergeSort(int[] arr, int lo, int hi) {
        // for counting operations
        int count = 0;

        // calculate length of part to be sorted
        int length = hi - lo;

        // if there's more than one element to be sorted
        if (length > 1) {
            // split the range in two equal parts
            int halfLength = length / 2;
            int mid = lo + halfLength;

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

            // merge the sublists and print out the result
            count += merge(arr, lo, mid, hi);
        }

        return count;
    }

    /**
     * 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 int merge(int[] arr, int lo, int mid, int hi) {
        int count = 0;
        int[] firstHalf = Arrays.copyOfRange(arr, lo, mid);
        int[] lastHalf = Arrays.copyOfRange(arr, mid, hi);
        int[] result = Arrays.copyOfRange(arr, lo, hi);
        count += merge(result, firstHalf, lastHalf);
        for (int i = 0; i < result.length; ++i) {
            ++count;
            arr[lo+i] = result[i];
        }
        return count;
    }

    /**
     * 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 int merge(int[] result,
                             int[] onePart,
                             int[] otherPart) {
        int count = 0;
        int i = 0;
        int j = 0;
        int k = 0;

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

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

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

        return count;
    }

    /**
     * Ask the user if they'd like to continue.
     *
     * @return true if the user wants to continue; false otherwise
     */
    private static boolean userContinue() {
        System.out.print("\nPress ENTER to continue or N or Q to quit: ");
        return KBD.nextLine().isEmpty();
    }

    /**
     * Calcuilate how many operations we'd expect for insertion sort in the worst
     * case.
     *
     * @param len the length of the list
     * @return the expected number of operations for insertion-sorting a list of
     * the given length
     */
    private static int expected(int len) {
        return (int)Math.ceil(5 * len * Math.log(len)/Math.log(2) / 2);
    }

}