Marc Hosang Marc Hosang - 5 months ago 13
Java Question

Recursive Merge Sort Java Program

I've been working on a merge sort recursive code and I've hit a speed bump. I've gone through the internet and my algorithm itself on paper MANY times and I just can't seem to figure out the problem.

public static int[] mergesort(int[] data, int low, int high)
{
int middle = (high+low)/2;
if (middle==low)
{
int[] data2 = new int [1];
data2[0]=data[middle];
return data2;
}
else
{
int[] firstHalfSorted = mergesort(data, low, middle);
int[] secondHalfSorted = mergesort(data, middle+1, high);
return (merge(firstHalfSorted, secondHalfSorted));
}
}

public static int[] merge(int[] firstHalfSorted, int[] secondHalfSorted)
{
int[] SortedArray = new int[firstHalfSorted.length+secondHalfSorted.length];
int m = 0;
int n = 0;
int count = 0;
while (m<firstHalfSorted.length && n<secondHalfSorted.length)
{
if (firstHalfSorted[m]>secondHalfSorted[n])
{
SortedArray[count]=secondHalfSorted[n];
count++;
n++;
}
else if (firstHalfSorted[m]<secondHalfSorted[n])
{
SortedArray[count]=firstHalfSorted[m];
count++;
m++;
}
}
if (m!=firstHalfSorted.length)
{
while(m<firstHalfSorted.length){
SortedArray[count]=firstHalfSorted[m];
count++;
m++;
}
}
if (n!=secondHalfSorted.length)
{
while(n<secondHalfSorted.length){
SortedArray[count]=secondHalfSorted[n];
count++;
n++;
}
}
return SortedArray;
}


There's the code. The problem is from a text input file with numbers, 3,9,7,2,10,5,1,8 in that order, the code only sorts every other number, being 3,7 and 10,1, then 3,7,1,10.

By all my thinking it should sort 3,9 then 7,2 and so on then, 3,9,7,2 and 10,5,1,8 and so on and so on, but it does not! Can you guys help me out here?

Answer

As far as I can tell, the problematic code is:

if (middle==low)
{
    int[] data2 = new int [1];
    data2[0]=data[middle];
    return data2;
}

This code will return one element array when high-low<=1. So, for low = 0, high=1 method will return zeroth element when it expected to return sorted two-element array. You can change it to:

if(low==high) //one element passed
//same here