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;
Merge sort on an Integer class
java;performance;sorting;mergesort
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 < array.length; i++){            System.out.print(array[i] +  );        }        System.out.println();    }    private static int[] mergeSort(int[] a, int p, int q)     {        if (q-p < 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 <= mid && rightHead <= 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] > 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 <= right && (bufferSize - bufferIndex) > 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.