//Recursive mergesort
    //This method recrursively sorts the section of the array from start to "end", Inclusive
    public void Merge_Sort (int[] array, int start, int end)
    {
        //Calculate the length of this range of the array
        int length = end - start + 1;

        //If the length is 1, there's no work to do
        //So return 0
        if (length <= 1)
        {
            return;
        }


        //If the length is 2, check to see if the values are out of order, and if so, swap them.
        //Return 1
        if (length == 2)
        {
            if (array [start] > array [end])
            {
                int temp = array [start];
                array [start] = array [end];
                array [end] = temp;
            }
        }


        //Find the middle of the range
        int mid = (start + end) / 2;

        //Mergesort the left half
        Merge_Sort (array, start, mid);

        //Mergesort the right half
        Merge_Sort (array, mid + 1, end);


        c.println ("LEFT");
        //Copy the left half of the range into a new array
        int[] left = new int [mid - start + 1];

        for (int i = 0 ; i < left.length ; i++)
        {
            left [i] = array [i];
            c.print (left [i] + " ");
        }

        c.println ("\nRIGHT");
        //Copy the right half of the range into a new array
        int[] right = new int [end - mid];

        for (int i = 0 ; i < right.length ; i++)
        {
            right [i] = array [i + mid + 1];
            c.print (right [i] + " ");
        }

        c.getChar ();

        //Merge the left and right halves
        Merge (left, right);

        //Copy the results of the merge back into the main array
        for (int i = 0 ; i < tempArr.length ; i++)
        {
            array [i] = tempArr [i];
        }

        //Return a value indicating how much work was done.
    }


    //This method merges two arrays of integers, and returns the result in a new array
    //We are assuming that the two lists are each already sorted
    protected void Merge (int[] left, int[] right)
    {
        //Create a new array to store the results (must be big enough to hold all the values left and right)
        tempArr = new int [left.length + right.length - 1];

        //Create a variable to track where we are in each array (leftIndex and rightIndex)
        int leftIndex = 0;
        int rightIndex = 0;

        //Loop from the start of out result array to the end
        for (int i = 0 ; i < tempArr.length ; i++)

            {
                //If leftIndex is more than the length of the "left" array, copy the value of "right" array into the result array, and increase rightIndex by 1
                if (leftIndex >= left.length)
                {
                    tempArr [i] = right [rightIndex];
                    rightIndex++;
                }

                //Else if the rightIndex is more than the length of the "right" array, copy the value of the "left" array into the result array, and increase leftIndex by 1
                else if (rightIndex >= right.length)
                {
                    tempArr [i] = left [leftIndex];
                    leftIndex++;
                }

                //Else if  the value in the "left" array is less than the value in the "right" array, copy the value in the "left" array into the result array, increase leftIndex by 1
                else if (left [leftIndex] < right [rightIndex])
                {
                    tempArr [i] = left [leftIndex];
                    leftIndex++;
                }

                //Else copy the value in the "right" array into the result array, and increase rightIndex by 1
                else
                {
                    tempArr [i] = right [rightIndex];
                    rightIndex++;
                }

                //End if

                //End loop
            }
    }

int mid = (start + end) / 2;