DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

1. Registered User
Join Date
Dec 2005
Posts
27

MergeSort

I am having trouble writing a mergesort.
Here is the alogorithm that i need to use
Code:
```
# /**
* recursive mergesort of an array of integers
*
* @param a reference to an array of integers to be sorted
* @param first starting index of range of values to be sorted
* @param last ending index of range of values to be sorted
*/
void recursiveMergeSort (int [ ] a, int first, int last)
// Recursively divides a list in half, over and over. When the
// sublist has one or two values, stop subdividing.
{
if (sublist has only one value)
do nothing
else if (sublist has two values)
sort it if necessary
else // recursion, divide list into two halves
Find midpoint of current sublist
Call recursiveMergeSort and process left sublist
Call recursiveMergeSort and process right sublist
merge left and right sublists
}
# You will also have to write the code for method:

private void merge (int [ ] a, int first, int mid, int last)
{
// Replace this line with your code
}```
Here is what i have so far.

Code:
```
public void mergeSort(int a[], int first, int last)
{
if(last > first)
{
return;
}
else if(a[last] == a[first +1])
{
for(int i = 0; i <= a.length -1 ; i ++)
{
if(a[i] > a[i+1])
{
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
}
}
}
else
{
int mid = (first + last)/2;
mergeSort(a, first, mid);
mergeSort(a, mid, last);

}
}```

2. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
You're missing the whole "take 'em apart and put them back together again" which is the basis of the merge sort - THERE IS NO SWAPPING INVOLVED.

You recursively break down the parts, by two, until they are single, then you stitch the parts back together into larger and larger parts, merging them so they are in "order"

16->(2-8's)->(4-4's)->(8-2's)->(16-1's)
then
(16-1's)->(8-2's)->(4-4's)->(2-8's)->1-16

when you are down to 1, you take each pair of runs and decide - which of the elements which is "first" in each run is the "less than the other"? That is the one which gets merged back into the larger run first. When that is moved, then compare which is "first" again, and copy that. Keep going until you've depleted both runs - there is a trick here - you'll have three conditions: both sub arrays have elements, only the "left" array has elements, only the "right" array has elements ... and then you have completed the merge back in.

For your recursive procedure, you will be performing an "in place" merge sort, ultimately writing back into your original array. The procedure will take your array - parent -, break it into two parts - child 1, child 2, break out child1 into grandchild 1 and 2, then grandchild 1 into greatgrandchild 1 and 2, until you are down to a pair of decendant arrays of length 1. Then write back the lesser of each, into its parent array, and continue on up, until you have returned to your original array.

Since you are using arrays rather than lists, you will need some help in handling the arrays. Keep the System.arraycopy method in mind to create your child arrays. Also, you will have to iterate yourself through the child arrays while you are merging back - you don't want to delete and rewrite, etc. - pretty messy. So you'll need to keep track of where you are in each array. Do you know how to create and use an iterator in the array? This also allows you to test whether the array has anything left, using the iterator's hasNext() method. If not, you can approximate the action of an iterator by increasing the index of the array in question until you have reached the length of the array.

Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise