Merge sort on an Integer class

Question

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;

Answer 1

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.

Answer 2

If performance is the only criteria that you want, then you can use threads to paralyze the merging part of it. To copy an array there is a simple way to use Arrays.copyOf().

Here is the code that includes thread and the use of array as reference:

Integer[] array;

public MergeSort(Integer[] array) {
    this.array = array;
}

public void run() 
{
    if (this.array.length <= 1) return;
    int mid = (int)Math.ceil((this.array.length)/2.0);
    Integer[] left = new Integer[mid];
    Integer[] right = new Integer[this.array.length - mid];

    left = Arrays.copyOf(array, mid);
    right = Arrays.copyOfRange(array, mid, array.length);

    Thread t1 = new MergeSort(left);
    Thread t2 = new MergeSort(right);
    t1.run();
    t2.run();
    try {
        t1.join();
        t2.join();
    } catch (InterruptedException e) {
    }

    merge(left, right);
}

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

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

public static void main(String[] args) throws InterruptedException {
    Integer[] unordered = new Integer[]{12,1,34,22,13,54,2,6,3};
    MergeSort merger = new MergeSort(unordered);
    merger.start();
    merger.join();
    System.out.println(Arrays.asList(merger.array));

}