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 &lt;= 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 &lt; left.length; i++)
    {
        left[i] = a[index++];
    }
    for (int i = 0; i &lt; 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 &lt; a.length || j &lt; b.length)
    {
        if (i != a.length &amp;&amp; j != b.length)
        {
            if (a[i].compareTo(b[j]) &lt;= 0)
            {
                result[k++] = a[i++];
            }
            else
            {
                result[k++] = b[j++];
            }
        }
        else if (i &lt; a.length)
        {
            result[k++] = a[i++];
        }
        else if (j &lt; 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 &lt; array.length; i++){
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }

    private static int[] mergeSort(int[] a, int p, int q) 
    {
        if (q-p &lt; 1) return a;
        int mid = (q+p)/2;

        mergeSort(a, p, mid);
        mergeSort(a, mid+1, q);
        return merge(a, p, q, mid);
    }

    private static int[] merge(int[] a, int left, int right, int mid) 
    {
        //buffer - in the worst case, we need to buffer the whole left partition
        int[] buffer = new int[a.length / 2 + 1];
        int bufferSize = 0;
        int bufferIndex = 0;
        int leftHead = left;
        int rightHead = mid+1;

        //we keep comparing unless we hit the boundary on either partition
        while(leftHead &lt;= mid &amp;&amp; rightHead &lt;= right){
            //no data in the buffer - normal compare
            if((bufferSize - bufferIndex) == 0){
                //right is less than left - we overwrite left with right and store left in the buffer
                if(a[leftHead] &gt; 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] &gt; 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 &lt;= right &amp;&amp; (bufferSize - bufferIndex) &gt; 0){
            if(rightHead &lt;= right &amp;&amp; a[rightHead] &lt; buffer[bufferIndex]){
                a[leftHead] = a[rightHead];
                rightHead++;
            }
            else{
                if(leftHead &lt;= 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.