9 Replies Latest reply: Mar 13, 2009 12:18 PM by 843785

# Merge Sort Algorithm

Hi, i'm trying to write merge sort methods but I have 2 problems, here's the mergesort method, and then the merge method below where I have some problems:
``````public static void mergesort(int[] array, int first, int last)
{
if (last-first > 1)
{
int mid = (first + last)/2;
mergesort(array, first, mid); //recursive call 1
mergesort(array, mid, last); //recusive call 2
merge(array, first, mid, last);
}
}``````
``````public static void merge(int[] array, int first, int mid, int last) {
//merge array[first to mid-1] and array[mid to last-1]
int leftpos = first;
int rightpos = mid;
int newpos = 0;
int[] temparray = new int[x];//<------- What should the size of x be?
while(leftpos<mid && rightpos<=(last-1)) {
if (array[leftpos] <= array[rightpos]) {
temparray[newpos] = array[leftpos];
leftpos++; newpos++;
}
else {
temparray[newpos] = array[rightpos];
rightpos++; newpos++;
}
while(leftpos<mid){   //copy the rest of left half
temparray[newpos] = array[leftpos];
leftpos++; newpos++;
}
while(rightpos<=last-1) {   //copy the rest of right half (
temparray[newpos] = array[rightpos];
rightpos++; newpos++;
}
//          copy temparray to array[first to (last-1)]   <---- how do I do this?
}
}``````
Any help?

Thank you.
• ###### 1. Re: Merge Sort Algorithm
Would you think it be useful to us if you explained what freakin problems your having
• ###### 2. Re: Merge Sort Algorithm
Melanie_Green wrote:
Would you think it be useful to us if you explained what freakin problems your having
Probably freakin out because it is due today.
• ###### 3. Re: Merge Sort Algorithm
Melanie_Green wrote:
Would you think it be useful to us if you explained what freakin problems your having
The two freaking problems are marked in the OP supplied code.
• ###### 4. Re: Merge Sort Algorithm
lol yeah maybe I should have been more clear.. but the 2 problems I am having are commented in the second method.
• ###### 5. Re: Merge Sort Algorithm
coldfire- wrote:
Hi, i'm trying to write merge sort methods
Because sorting algorithms are so thouroughly analysed and because the internet is full of Java implementations I feel helping you with debugging details is kind of wasted effort. To learn something you should do the debugging. If you want a working implementation just take your pick from the internet smorgasbord.
• ###### 6. Re: Merge Sort Algorithm
Seems you're trying to combine the "divide" step with the "conquer" step in the merge. I recently wrote a merge sort for one of my applications for alphabetizing. I followed Wikipedia's pseudocode and it was a piece of cake.

If you're using ArrayList (like I did) for the dividing, don't use remove(0) to shave the first item off after you're done with it in the loop(s) like the pseudocode seems to suggest because that causes all the indexes to shift. I cut a full 2 seconds off (down to 0 seconds) of a 75k word list sort by using ints as counters to go through the lists.

http://en.wikipedia.org/wiki/Merge_sort#Algorithm

Edited by: kavon89 on Mar 12, 2009 9:51 PM
• ###### 7. Re: Merge Sort Algorithm
kavon89 wrote:
Seems you're trying to combine the "divide" step with the "conquer" step in the merge. I recently wrote a merge sort for one of my applications for alphabetizing. I followed Wikipedia's pseudocode and it was a piece of cake.

If you're using ArrayList (like I did) for the dividing, don't use remove(0) to shave the first item off after you're done with it in the loop(s) like the pseudocode seems to suggest because that causes all the indexes to shift. I cut a full 2 seconds off (down to 0 seconds) of a 75k word list sort by using ints as counters to go through the lists.

http://en.wikipedia.org/wiki/Merge_sort#Algorithm

Edited by: kavon89 on Mar 12, 2009 9:51 PM
I was able to get my merge sort to work, but with the wordlist i'm using (150,000+ words) it is considerably slow! How does your algorithm compare with a word list of that size?
• ###### 8. Re: Merge Sort Algorithm
kavon89, i'm trying to write the methods from the pseudocode on that Wikipedia website. I wrote the mergesort method (hope it's right):
``````public ArrayList<String> merge_sort(ArrayList<String> m) {
ArrayList<String> left = new ArrayList<String>();
ArrayList<String> right = new ArrayList<String>();
ArrayList<String> result = new ArrayList<String>();
if (m.size() <= 1)
return m;
else {
// This calculation is for 1-based arrays. For 0-based, use length(m)/2 - 1.
int middle = m.size() / 2;
for(int x = 0; x < middle; x++)
for(int y = middle; y < m.size(); y++)
left = merge_sort(left);
right = merge_sort(right);
result = merge(left, right);
return result;
}
}``````
But now I am having trouble writing the merge method, from this pseudocode:
``````function merge(left,right)
var list result
while length(left) > 0 and length(right) > 0
if first(left) &#8804; first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
end while
while length(left) > 0
append left to result
while length(right) > 0
append right to result
return result``````
I have:
``````public ArrayList<String> merge(ArrayList<String> left,ArrayList<String> right) {
ArrayList<String> result;
while(left.size() > 0 && right.size() > 0) {
.....``````
so far.. not really sure how to write the rest from that pseudocode. Perhaps you can give me some pointers?
• ###### 9. Re: Merge Sort Algorithm
``````function merge(left,right)
var list result //this is the list which be added to
while length(left) > 0 and length(right) > 0
if first(left)  first(right) //if the item in the "left" list is smaller than the right
append first(left) to result //add the left one to the result (decending order)
left = rest(left) //then remove it, or rather advance your index for the left side's list
else
append first(right) to result //otherwise obviously do the same as the above but for the right list
right = rest(right)
end while

//now one of the lists has emptied up, time to add the leftovers which are already in order

while length(left) > 0
append left to result
while length(right) > 0
append right to result
return result``````
Edited by: kavon89 on Mar 13, 2009 1:18 PM