Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite

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. The question is how do I merge sort without copying? The sorting must be stable and both methods should return Integer[].

Here's my code:

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;
share|improve this question
 
The algorithm looks correct to me. Merge sort requires you to split the array which doesn't really happen without copying to two new arrays at some point so I don't think that's your issue. You could try doing it with an int[] instead of an Integer[]. Java might like its primitive types better –  mattedgod Mar 22 '12 at 23:31
 
Given that this is not a homework, why don't you just use the Arrays.sort() stuff? That is a merge sort. (Provided you convert array of Integers to array of ints, but that's just O(n), less than O(nlogn) merge sort.) –  Jakub Zaverka Mar 22 '12 at 23:39
 
I can actually write two void methods for sorting ints but this question requires me to return an array of type Integer[]. –  user1175946 Mar 22 '12 at 23:41
1  
@Jakub Zaverka: Arrays.sort is using quick sort. I'm trying to compare it with my program. –  user1175946 Mar 22 '12 at 23:45
1  
@user1175946 Oh, good one, I thought they are using mergesort. Anyway, if you use sort(T[] a, Comparator<? super T> c), then it is mergesort (just checked). You only need to provide an implementation of Comparable<Integer>, which should be trivial. –  Jakub Zaverka Mar 22 '12 at 23:52
show 5 more comments

migrated from stackoverflow.com Mar 23 '12 at 12:31

This question came from our site for professional and enthusiast programmers.

2 Answers

up vote 2 down vote accepted

Why this continuous migrating? You are tearing SO apart into tons of different sites that nobody will use.

Anyway, since my answer disappeared in the process, I enclose the full code now:

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;
    }
}

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.

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

share|improve this answer
up vote 0 down vote

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));

}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.