• Post Reply Bookmark Topic Watch Topic
  • New Topic

MergeSort  RSS feed

 
Jay Kamdar
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I am trying to do mergesort without breaking the orginal in pieces and i can't understand what is wrong.

[ December 04, 2005: Message edited by: Jim Yingst ]
 
Scott Selikoff
author
Bartender
Posts: 4093
21
Eclipse IDE Flex Google Web Toolkit
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thank You, Our teacher was not very specific about the extra arrays. All he said that don't use arraycopy.
 
Stefan Evans
Bartender
Posts: 1837
10
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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 ]
 
Consider Paul's rocket mass heater.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!