Merge sort on an Integer class

This is a specific case in merge sort. I'm trying to do a merge sort on an array that's created using the Java Integer class. My implementation is slow and therefore needs some modifications for better performance. I believe the process where I copy the original items to two new arrays over and over again is slowing it down.

How do I merge sort without copying? The sorting must be stable and both methods should return Integer[].

private static Integer[] mergeSort(Integer[] a, int p, int q) 
{
    if (a.length <= 1) return a;

    int mid = (int)Math.floor((q-p)/2);
    Integer[] left = new Integer[(mid - p) + 1];
    Integer[] right = new Integer[q - mid];
    int index = 0;

    for (int i = 0; i < left.length; i++)
    {
        left[i] = a[index++];
    }
    for (int i = 0; i < right.length; i++)
    {
        right[i] = a[index++];
    }

    left = mergeSort(left, 0, left.length-1);
    right = mergeSort(right, 0, right.length-1);
    return merge(left, right);
}

private static Integer[] merge(Integer[] a, Integer[] b) 
{
    int i = 0; int j = 0; int k = 0;

    Integer[] result = new Integer[a.length+b.length];

    while (i < a.length || j < b.length)
    {
        if (i != a.length && j != b.length)
        {
            if (a[i].compareTo(b[j]) <= 0)
            {
                result[k++] = a[i++];
            }
            else
            {
                result[k++] = b[j++];
            }
        }
        else if (i < a.length)
        {
            result[k++] = a[i++];
        }
        else if (j < b.length)
        {
            result[k++] = b[j++];
        }
    }

    return result;

It was quite hard, but I figured it out. You can even pre-create the buffer with some value you know the mergesort will never exceed, and save some object creation overhead.

public class Mergesort
{
    public static void main(String[] args){
        int[] array = new int[]{1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
        array = mergeSort(array, 0, array.length-1);
        for(int i = 0; i  a[rightHead]){
                    buffer[bufferSize] = a[leftHead];
                    a[leftHead] = a[rightHead];
                    bufferSize++;
                    rightHead++;
                }
            }
            //some data in the buffer - we use buffer (instead of left) for comparison with right
            else{
                //right is less than buffer
                if(buffer[bufferIndex] > a[rightHead]){
                    //we overwrite next left value, but must save it in the buffer first
                    buffer[bufferSize] = a[leftHead];
                    a[leftHead] = a[rightHead];
                    rightHead++;
                    bufferSize++;
                }
                //buffer is less than right = we use the buffer value (but save the overwriten value in the buffer)
                else{
                    buffer[bufferSize] = a[leftHead];
                    a[leftHead] = buffer[bufferIndex];
                    bufferSize++;
                    bufferIndex++;
                }
            } 
            leftHead++;
        }
        //now we hit the end of either partition - now we have only two of them (buffer and either left or right)
        //so we do traditional merge using these two
        while(leftHead  0){
            if(rightHead <= right && a[rightHead] < buffer[bufferIndex]){
                a[leftHead] = a[rightHead];
                rightHead++;
            }
            else{
                if(leftHead <= mid){
                    buffer[bufferSize] = a[leftHead];
                    bufferSize++;
                }
                a[leftHead] = buffer[bufferIndex];
                bufferIndex++;
            }
            leftHead++;
        }
        return a;
    }
}

I did not extensively test it, nor did I measure it. You can try that and post the results.

StackExchange Code Review Q#10276, answer score: 2