• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Tim Cooke
  • Campbell Ritchie
  • Ron McLeod
  • Junilu Lacar
  • Liutauras Vilda
Sheriffs:
  • Paul Clapham
  • Jeanne Boyarsky
  • Henry Wong
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Piet Souris
  • Carey Brown
Bartenders:
  • Jesse Duncan
  • Frits Walraven
  • Mikalai Zaikin

MergeSort

 
Greenhorn
Posts: 22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 ]
 
author
Posts: 4323
39
jQuery Eclipse IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Bartender
Posts: 1845
10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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 ]
 
reply
    Bookmark Topic Watch Topic
  • New Topic