Help With MergeSort

[whoareyou]

I have a somewhat working merge sort class (I fixed the stack over flow problem) that can perform merge sort (obviously). I think that after many trials, I've gotten it to work with 4 numbers (100% correct). However, when I try anything that is 5 and above (ie. 5 numbers in the array or more) it fails. Sometimes it works (I've been testing with 5 only) and sometimes it doesn't. For example, it sorts "0 2 3 4 0" right, but it doesn't sort "3 0 1 2 1" properly. It outputs "0 1 1 1 2". I think something is wrong with the indexes somewhere because in most cases, it is just one number that is being overwritten with another one in the array. I am, however, unable to diagnose the problem so I was hoping someone could tell me what is wrong in the code:

code:

//Recursive mergesort     //This method recrursively sorts the section of the array from start to "end", Inclusive     public void Merge_Sort (int[] array, int start, int end)     {         //Calculate the length of this range of the array         int length = end - start + 1;         //If the length is 1, there's no work to do         //So return 0         if (length <= 1)         {             return;         }         //If the length is 2, check to see if the values are out of order, and if so, swap them.         //Return 1         if (length == 2)         {             if (array [start] > array [end])             {                 int temp = array [start];                 array [start] = array [end];                 array [end] = temp;             }         }         //Find the middle of the range         int mid = (start + end) / 2;         //Mergesort the left half         Merge_Sort (array, start, mid);         //Mergesort the right half         Merge_Sort (array, mid + 1, end);         c.println ("LEFT");         //Copy the left half of the range into a new array         int[] left = new int [mid - start + 1];         for (int i = 0 ; i < left.length ; i++)         {             left [i] = array [i];             c.print (left [i] + " ");         }         c.println ("\nRIGHT");         //Copy the right half of the range into a new array         int[] right = new int [end - mid];         for (int i = 0 ; i < right.length ; i++)         {             right [i] = array [i + mid + 1];             c.print (right [i] + " ");         }         c.getChar ();         //Merge the left and right halves         Merge (left, right);         //Copy the results of the merge back into the main array         for (int i = 0 ; i < tempArr.length ; i++)         {             array [i] = tempArr [i];         }         //Return a value indicating how much work was done.     }     //This method merges two arrays of integers, and returns the result in a new array     //We are assuming that the two lists are each already sorted     protected void Merge (int[] left, int[] right)     {         //Create a new array to store the results (must be big enough to hold all the values left and right)         tempArr = new int [left.length + right.length - 1];         //Create a variable to track where we are in each array (leftIndex and rightIndex)         int leftIndex = 0;         int rightIndex = 0;         //Loop from the start of out result array to the end         for (int i = 0 ; i < tempArr.length ; i++)             {                 //If leftIndex is more than the length of the "left" array, copy the value of "right" array into the result array, and increase rightIndex by 1                 if (leftIndex >= left.length)                 {                     tempArr [i] = right [rightIndex];                     rightIndex++;                 }                 //Else if the rightIndex is more than the length of the "right" array, copy the value of the "left" array into the result array, and increase leftIndex by 1                 else if (rightIndex >= right.length)                 {                     tempArr [i] = left [leftIndex];                     leftIndex++;                 }                 //Else if  the value in the "left" array is less than the value in the "right" array, copy the value in the "left" array into the result array, increase leftIndex by 1                 else if (left [leftIndex] < right [rightIndex])                 {                     tempArr [i] = left [leftIndex];                     leftIndex++;                 }                 //Else copy the value in the "right" array into the result array, and increase rightIndex by 1                 else                 {                     tempArr [i] = right [rightIndex];                     rightIndex++;                 }                 //End if                 //End loop             }     }

[2goto1]

When you say that you're unable to try and diagnose the problem, what have you tried to diagnose the problem with? How did you conclude that you're unable to diagnose the problem?

This line:

code:

int mid = (start + end) / 2;

Looks like integer division. With integer division operations in Java, remainders are truncated. 3 / 2 = 1. Could that be an issue?

[whoareyou]

Ok so I fixed one part: there was something wrong in the merge method with the length of the temp array. I wrote a program to test the actual merging process and it seems to work. So now, its clearly something wrong in the Merge_Sort method.

The integer division has already been taken care of. That's why there's the +1 when calling the merge_sort for the right portion of the split array.