public class MergeSort
{
    public static final void main(String[] args)
    {
        int[] array = {3,4, 5, 3, 2, 1};

        System.out.println("Not Sorted:");
        for (int i = 0; i < array.length; i ++)
        {
            System.out.println("array[" + i + "] = " + array[i]);
        }

        array = sort(array);

        System.out.println("Sorted:");
        for (int i = 0; i < array.length; i ++)
        {
            System.out.println("array[" + i + "] = " + array[i]);
        }

    }

    public static int[] sort(int[] array)
    {
        // base case: list only has 1 element
        if (array.length == 1)
            return array;

        // otherwise, split in half
        int[] leftArray = splitArray(array, false);
        int[] rightArray = splitArray(array, true);

        // recursively sort the left half
        leftArray = sort(leftArray);
        // recursively sort the right half
        rightArray = sort(rightArray);

        // merge the two sorted halves and return the result
        return merge(leftArray, rightArray);
    }

    private static int[] splitArray(int[] array, boolean returnUpperHalf)
    {
        int start = -1, end = -1;
        
        if (returnUpperHalf)
        {
            start = 0;
            end = array.length / 2;
        }
        else
        {
            start = array.length / 2;
            end = array.length;
        }

        int size = end - start;

        int[] halfArray = new int[end - start];
        for (int i = 0; i < size; i ++)
        {
            halfArray[i] = array[start + i];
        }

        return halfArray;
    }

    /**
     * This is the only place you need to change anything.
     */
    private static int[] merge(int[] a1, int[] a2)
    {
        // This is just junk code so that it will compile;
        // you need to replace it with your own code.
        int[] a = new int[0];
        return a;
    }
}