Java recursion and Merge Sort

Question

Hi y'all,

I'm trying to write a simple merge sort program in Java, I'm seeing a lot of red in Eclipse. I'm still a beginner, and don't quite see whats wrong. thanks.

-Kyle

public class merge{ 
public static int[] mergeSub(int[] array, int left, int right){
     if(left<right)
     {
        int mid = (left+right)/2;
        int[] a = mergeSub(array, left, mid);
        int [] b = mergeSub(array, mid+1, right);
        return merge(a, b);

}
     int[] arr=new int[1];
     arr[0]=arr[left];
     return arr;
}

static int[] merge(int[] left, int[] right){
        int index =0; int indexLeft =0; int indexRight=0;
        int[] result = new int[left.length+right.length];

        while(indexLeft<left.length && indexRight<right.length){
                if(left[indexLeft] <= right[indexRight])
                {
                        result[index]=left[indexLeft];
                        index++;
                        indexLeft++;

                }
                else{
                        result[index]=right[indexRight];
                        index++;
                        indexRight++;
                }
        }

        if (indexLeft<left.length){
                while(indexLeft<left.length){
                        result[index]=left[indexLeft];
                        indexLeft++; index++;
                }
        }
        if (indexRight<right.length){
                while(indexRight<left[indexRight]){
                        result[index]=right[indexRight];
                        indexRight++; right[indexRight]++;
                }
        }
        return result;
}



public static void main(String args[]){

        int[] array = {2, 4, 5, 7, 5, 6, 3, 5, 7, 8};
        System.out.println(mergeSub(array, 0, 9));
}}

Answer 1

You should start by making it less red in Eclipse :-)

When you mouse over the error, it tells you what the error is. For example, in your mergeSub code you're declaring left and right as local arrays even though left and right are already declared as int parameters. Name your local variables differently.

Rinse and repeat.

Answer 2

My Java's a bit rusty, but I believe that in Java, EVERYthing must be in a class. You don't seem to declare any classes in your code sample, but maybe you just left them out for brevity?

Answer 3

First off... your main function mergeSub is declared as a static (which is fine) but you can't call non-static functions. Either make merge static, or make mergeSub a method of the containing class.

Answer 4

Copy/paste is your evil. I don't want to show the whole working code, so:

in mergeSub:

arr[0]=arr[left]; should be arr[0]=array[left];

in merge:

while(indexRight < left[indexRight]) should be while(indexRight < right.length)

right[indexRight]++; should be index++;

maybe there was more. Oh, and you can not print an array with println() you have to iterate through it.

Answer 5

I can see one problem (though it doesn't explain the compile-time errors):

mergeSub() does not check for being passed an empty array. If you do pass it an empty array you will get an ArrayIndexOutOfBoundsException at the arr[0]=array[left]; statemnt

Answer 6

After you've gotten rid of the red, based on the feedback given, you can compare your implementation with this one @ codecodex.com to see how it stacks up and learn some more.