Merge sort on an Integer class
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.