First attempt at mergeSort: can someone tell me what I did wrong?
It appears to be working for *some* arrays. But for the array below, it ends up with a bunch of null values. I have been debugging this **** for 2 hours. I still can't pinpoint the error. Can someone please give me a hand?
class MergeSort{
publicstaticint[] mergeSort(int[] array){
if (array.length <= 1)return array;
int key = array.length / 2;
int[] left =newint[key];
for (int x = 0; x < key; x++) left[x] = array[x];
int[] right =newint[array.length - key];
for (int x = 0; x < array.length - key; x++) right[x] = array[key + x];
return merge(mergeSort(left), mergeSort(right));
}
publicstaticint[] merge(int[] left,int[] right){
int[] merged =newint[left.length + right.length];
int l = 0, r = 0, p = 0;
while(l < left.length && r < right.length)
merged[p++] = ((left[l] <= right[r]) ? left[l++] : right[r++]);
if (l > r)for (int x = r; x < right.length; x++) merged[p++] = right[x];
elsefor (int x = l; x < left.length; x++) merged[p++] = left[x];
return merged;
}
publicstaticvoid main (String[] args){
int[] array ={8, 3, 2, 1, 5, 8, 7, 8, 5};
for (int x : array) System.out.print(x +" "); System.out.println(" ");
for (int x : mergeSort(array)) System.out.print(x +" "); System.out.println(" ");
}
}
[3232 byte] By [
Chapsa] at [2007-11-26 21:11:09]
Sorry, all those one-character variable names and the ++ operator running amuck make that into write-only code. In other words, it's very hard to understand.
So my suggestion would be to run it for smaller arrays and see if there are systematic problems that you can see in the output. Or put in some debugging code so you can see what it's doing, step by step.
Edit: And what do you mean by "null values"? You only have ints there, the only things I can see that could be null are the array variables. And I don't see how that can be happening, you always initialize them.
Message was edited by:
DrClap
> Sorry, all those one-character variable names and the
> ++ operator running amuck make that into write-only
> code. In other words, it's very hard to understand.
>
A more demagogic version of the program can be found below!
> So my suggestion would be to run it for smaller
> arrays and see if there are systematic problems that
> you can see in the output. Or put in some debugging
> code so you can see what it's doing, step by step.
>
This is supposed to be a simple program. The problem should be evident to anyone who understands merge sort.
> Edit: And what do you mean by "null values"? You only
> have ints there, the only things I can see that could
> be null are the array variables. And I don't see how
> that can be happening, you always initialize them.
>
0s.
For example, if I enter this:
8 3 2 1 5 8 7 8 5
I end up with this "sorted" array:
1 2 3 5 5 7 0 8 0
Where did the 0's come from? I don't know. That's what I am trying to understand.
class MergeSort{
public static int[] mergeSort(int[] array){
if (array.length <= 1) return array;
int middle = array.length / 2;
int[] left = new int[middle];
for (int x = 0; x < middle; x++) left[x] = array[x];
int[] right = new int[array.length - middle];
for (int x = 0; x < array.length - middle; x++) right[x] = array[middle + x];
return merge(mergeSort(left), mergeSort(right));
}
public static int[] merge(int[] left, int[] right){
int[] merged = new int[left.length + right.length];
/*"l" refers to the current position in the left array
whose value we are comparing against the value
at the current "r" position in the right array.
"p" is the current position of the new merged array*/
int l = 0, r = 0, p = 0;
while(l < left.length && r < right.length)
merged[p++] = ((left[l] <= right[r]) ? left[l++] : right[r++]);
if (l > r) for (int x = r; x < right.length; x++) merged[p++] = right[x];
elsefor (int x = l; x < left.length; x++) merged[p++] = left[x];
return merged;
}
public static void main (String[] args){
int[] array = {8, 3, 2, 1, 5, 8, 7, 8, 5};
for (int x : array) System.out.print(x + " "); System.out.println(" ");
for (int x : mergeSort(array)) System.out.print(x + " "); System.out.println(" ");
//1 2 3 5 5 7 0 8 0 <- Those 0's!!!!!
}
}
Well, it's pretty clear to me that the zeroes aren't getting into the arrays that you build in the "split" stage. So they must be sneaking in when you do the merge stage. I don't think you are putting zeroes in there, I think you are just omitting to put 8's in there (in your example).
This smells wrong to me:if (l > r) ...
because it isn't symmetrical. I can't see exactly what's going on but in some cases you aren't copying the last entry from the longer sub-array into the merged array, and based on your example, that seems to happen only when it was equal to an entry already in the merged array. That's where I would look.
> This smells wrong to me:if (l > r)
> ...
because it isn't symmetrical. I can't see
> exactly what's going on but in some cases you aren't
> copying the last entry from the longer sub-array into
> the merged array, and based on your example, that
> seems to happen only when it was equal to an entry
> already in the merged array. That's where I would
> look.
I am back to square 1. I have been staring at this algorithm for hours and still can't see where it's failing because everything *seems* right..
Can someone else see the problem?
> I am back to square 1. I have been staring at this
> algorithm for hours and still can't see where it's
> failing because everything *seems* right..
>
> Can someone else see the problem?
I think DrClap is right about the if (l > r)
tryif (l >= r)
instead.
DrClap, prometheuzz, YAT, thanks a lot for being more intelligent than I :)
In order to eliminate the ambiguity, I replaced the if (l > r) then statement for two if statements:
if (l == left.length)
if (r == right.length)
And it works fine. Thanks a lot guys :)
By the way, I've noticed that some people write the mergeSort method passing only the array to be sorted and int values indicating the begin/middle/end positions used to split the array.
Why should that method be prefered over the method I used (it creates new arrays every time the original array is split in half and every time the two arrays are merged)?
Is it because the way I did it uses up too much memory?
Well, that other method that modifies the array in place does use less memory than your method that creates new arrays all the time. At each recursive call you create (essentially) two more arrays of the same size as the original array. So if my quick look at it is correct, the modify-in-place method is O(N) in memory usage and yours is O(N log N).
