current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 5 down vote favorite 
public class MergeSort {

    public static void sort(int[] array, int lo, int hi) {
        if (hi <= lo) {
            return;
        }

        int mid = lo + (hi - lo) / 2;
        sort(array, lo, mid);
        sort(array, mid + 1, hi);
        mergesort(array, lo, mid, hi);
    }

    private static void mergesort(int[] array, int lo, int mid, int hi) {
        int[] aux = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            aux[i] = array[i];
        }
        int i = lo;
        int j = mid + 1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                array[k] = aux[j++];
            } else if (j > hi) {
                array[k] = aux[i++];
            } else if (aux[i] > aux[j]) {
                array[k] = aux[j++];
            } else {
                array[k] = aux[i++];
            }
        }
    }

    public static void main(String[] args) {
        int[] a = { 3, 1, 5, 1, 8, 23, 55, 54, 10, 12, 5 };
        MergeSort.sort(a, 0, a.length - 1);
        show(a);
    }

    private static void show(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

}

It took me a whole day and a half to understand the code but I did a quick test and it worked. One thing I am concerned with is that the coursera class I am taking does it differently, instead of creating aux in mergesort they create aux in a helper class and pass around BOTH arrays in the sort and mergesort method. It looked like this:

private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
    if (hi <= lo) return;
    int mid = lo + (hi - lo) / 2;
    sort(a, aux, lo, mid);
    sort(a, aux, mid + 1, hi);
    merge(a, aux, lo, mid, hi);
}

/**
 * Rearranges the array in ascending order, using the natural order.
 * @param a the array to be sorted
 */
public static void sort(Comparable[] a) {
    Comparable[] aux = new Comparable[a.length];
    sort(a, aux, 0, a.length-1);
    assert isSorted(a);
}

and when it got to the merge sort method it finally copies the aux array, what is the point of this route? It looks like it just takes more code.

share|improve this question
up vote 6 down vote accepted

General comments

  • you have 'good' mid-finding code: int mid = lo + (hi - lo) / 2; This is fancy code, and, if you have not learned why it is done this way, then you should read up on the midpoint bug in Java.

  • your algorithm generally looks sound. It works

The basic premise of your sort is good. The code is neat, and, if you know the merge-sort, it is readable, and does the right sort of things at the right times.

With just your code in front of me, I would say 'good job'. To make it better, I would recommend that:

  • you make your code conform to the standard usage in Java, where you would have two methods:

    MergeSort.sort(int[] data);
MergeSort.sort(int[] data, offset, length);

    Java typically uses a 'length' argument, instead of a 'high' argument. In the case of the MergeSort, the 'high' variation is more useful, so I would recommend making your current method private, and then adding a new recursion-wrapping frontend to the code that makes it conform to typical Java method calls.

About the aux

This is the second reason to consider wrapping your current sort-entry method in to a calling method.... something like:

public static void sort(int[] data) {
    sort(data, 0, data.length);
}

public static void sort(int[] data, int offset, int length) {
    int[] aux = new int[data.length]; // smarter implementation can be used for if length != data.length
    recursiveSort(data, aux, offset, offset + length);
}

Where the method recursiveSort is the method you currently have as sort.

The reason for doing the aux in the calling method is for memory efficiency. At some point you will need to do the final merge, which will require the entire data array to fit in to a memory 'copy', the aux. You will also do many more smaller merge sorts requiring a smaller size of memory. If you are going to need the large space anyway, you may as well create it in the beginning, and reuse it many times, which is better than creating many small aux which never get reused.

share|improve this answer
1  
Thanks, couldn't have asked for a better response, really helpful. – gallly Feb 18 '14 at 21:27

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.