MergeSort

[Jay Kamdar]

I am trying to do mergesort without breaking the orginal in pieces and i can't understand what is wrong.

    public static void MergeSort(int[] array, int lower, int upper) 
    {
        if (lower >= upper)
        {
            
            return;
        }
        else
        {
            MergeSort(array, lower, ((upper + lower) / 2));
            MergeSort(array, ((upper + lower) / 2 + 1), upper);    
        }
        
        Merge(array, lower, ((upper + lower) / 2), ((upper + lower) / 2 + 1), upper);
    }
    
    private static void Merge(int[] array, int lower1, int upper1, int lower2, int upper2)
    {
        int[] tempArray = new int[upper2-lower1];
        int lower = lower1;
        int upper = upper2;
        int i = lower1;
        
        while (lower1 < upper1 && lower2 < upper2 && i < tempArray.length)
        {
            if (array[lower1] < array[lower2])
            { 
                tempArray[i] = array[lower1]; 
                lower1++;   
            }
            else
            {       
                tempArray[i] = array[lower2]; 
                lower2++; 
            }
            i++;
        }
        i = 0;
        for(int j = lower; j < upper; j++)
        {
            array[j] = tempArray[i];
            i++;
        }
    }

[ December 04, 2005: Message edited by: Jim Yingst ]

[Scott Selikoff]

At first glance, there seems to be some problem with your Merge() method not merging all data

Assume merge is called with the following params:

Merge(array,0,1,1,2) <-- implies a 2-element array divided in two.

(SIDE NOTE: upper1 is always the same as lower2 so you don't need to pass it, in fact they are both derivived from lower1 and upper2, so they aren't needed at all for passing)

Watch what happens after one execution of the while loop:

lower1 goes from 0 --> 1
-or-
lower2 goes from 1 --> 2

And since lower1 >= upper1 ( 1 >= 1) -or- lower2 >= upper2 ( 2 >= 1) the loop will execute exactly once. But, there were two elements to be merged! Therefore, one element may be over-ridden. The common solution is that after your while loop you should have two additional loops that copy missing data to the temp array from whichever array did not finish (if the loop terminates at least one array must be complete)

There may be more problems, but thats the only one that struct me right away. BTW note that you are cutting up the original array in some way since you are using a temporary array. Its not a true 'in-place' sort anyway.
[ December 04, 2005: Message edited by: Scott Selikoff ]

[Jay Kamdar]

Thank You, Our teacher was not very specific about the extra arrays. All he said that don't use arraycopy.

[Stefan Evans]

To get an understanding of your program, I recommend putting in a few debugging statements.

Heres some stuff that might help:

public static void printArray(int[] array){
if (array.length == 0){
System.out.println("empty list");
}
else{
System.out.print("[" + array[0]);
for(int i=1; i<array.length; i++){
System.out.print("," + array[i]);
}
System.out.println("]");
}
}

And then statements like these at the start/end of the methods - or anywhere else you want to put them...

System.out.println("Mergesort " + lower + " - " + upper);
System.out.print("Result: Mergesort " + lower + " - " + upper);
printArray(array);

System.out.println("Merging " + lower1 + " - " + upper1 + " and " + lower2 + " - " + upper2);

Some things to think about:
are lower1/upper1/lower2/upper2 inclusive or exclusive?
Ie if I say sort from lower1 to upper1 - does that include entry array[upper1]?
[ December 04, 2005: Message edited by: Stefan Evans ]