/* *****************************************************************************
 *
 *  Description:  MergeSort using Queues
 *
 **************************************************************************** */

public class QMerge {
    // ASSUMING a and b are sorted in increasing order, return a new queue
    // consisting of the elements of both in combined increasing order
    public static Queue<Integer> merge(Queue<Integer> a, Queue<Integer> b) {
        Queue<Integer> result = new Queue<Integer>();

        // keep going as long as there are elements to merge
        while (!a.isEmpty() && !b.isEmpty()) {
            // take the smaller element from either a or b, move it to result
            if (b.peek() < a.peek())
                result.enqueue(___.dequeue());
            else
                result.enqueue(___.dequeue());
        }

        // if anything is left over once one queue is empty, move it into result
        while (!a.isEmpty())
            result.enqueue(____.dequeue());
        while (!b.isEmpty())
            result.enqueue(____.dequeue());

        return result;
    }

    // return a new queue consisting of the same elements in sorted order
    public static Queue<Integer> mergeSort(Queue<Integer> input) {
        if (input.size() == ____) {  // base case
            Queue<Integer> result = new Queue<Integer>();
            result.enqueue(input.dequeue());
            return result;
        }
        else {
            // move half the elements into a new queue
            int halfSize = input.size() / 2;
            Queue<Integer> firstHalf = ___________;
            for (int i = 0; i < halfSize; i++)
                firstHalf._______(input._____());
            Queue<Integer> secondHalf = __________;
            // sort both halves and merge
            return merge(mergeSort(_______), mergeSort(_______));
        }
    }

    // read all integers from input, sort them, and print them
    public static void main(String[] args) {
        // input an some queue of int's
        Queue<Integer> data = new Queue<Integer>();
        while (!StdIn.isEmpty())
            data.enqueue(StdIn.readInt());

        // merge sort the input
        Queue<Integer> sortedData = mergeSort(data);

        // now print
        StdOut.println();
        StdOut.println("SORTED:");
        while (!sortedData.isEmpty())
            StdOut.println(sortedData.dequeue());
    }
}
