1 2 Previous Next 20 Replies Latest reply on Oct 22, 2008 8:07 PM by 793982

# Recursive mergeSort... small problem with infinate recursion.

Basically, I have made a recursive mergeSort method, but there is a small problem...im getting stuck with an eternal recursion, which is obviously followed up swiftly by a stack flow error, problem is I cant see where im going wrong...

Heres the code... any help is highly appreciated, as I am new to java, and this is for university.
``````public class part3
{

public static void main(String[] args)
{
// Declare array of unsorted values.
int[] values = {1,3,5,7,9,2,4,6,8,10};

// Display unsorted values on screen.
System.out.println("Unsorted Values");
for(int i= 0;i < values.length; i++)
{
System.out.println(values);
}

mergeSort(values, values.length);

output(values);

}

public static void mergeSort(int[] vals, int n)
{
// Declare necessary values

int lowCount, highCount;
int[] low, high;
int i, j, k;

if (n > 1)
{
low = new int[n];
high = new int[n];

for(i=0,j=0,k=0; i < n; i++)
{
if(vals[i] < low.length)

{
low[j] = vals[i];
j++;
}

else

{
high[k] = vals[i];
k++;
}

lowCount = j;
highCount= k;

mergeSort(low, lowCount);
mergeSort(high, highCount);

for(i = 0; i < lowCount; i++)
{
vals[i] = low[i];
}

for(i = 0; i < highCount; i++)
{
vals[i+lowCount] = high[i];
}

}
}
}

public static void output(int[] data)
{
for(int i = 0; i < data.length; i++)
{
System.out.print(data[i] + " ");
System.out.println();
}
}
}
``````
• ###### 1. Re: Recursive mergeSort... small problem with infinate recursion.
What you have attempted to write here is not a merge sort. Read about [Merge Sort|http://en.wikipedia.org/wiki/Merge_sort]
• ###### 2. Re: Recursive mergeSort... small problem with infinate recursion.
It's definitely not merge sort. You're mistakes aren't just Java, but logical.
Anyway, you can find complete [merge sort java implementation|http://www.java-tips.org/java-se-tips/java.lang/merge-sort-implementation-in-java.html] on google.
• ###### 3. Re: Recursive mergeSort... small problem with infinate recursion.
yes, thanks for the help guys, but dont you find that when you use any of the code off other sites that it doesnt compile?
• ###### 4. Re: Recursive mergeSort... small problem with infinate recursion.
Slip-1 wrote:
yes, thanks for the help guys, but dont you find that when you use any of the code off other sites that it doesnt compile?
Well, sometimes the code is really pseudo code, or is incomplete.
• ###### 5. Re: Recursive mergeSort... small problem with infinate recursion.
yes I know, problem is as i said earlier, Im not very experienced with java, this is an assignment, and I dont actually know where to start, Im very willing to learn, but like anyone, i need help in the right direction at times.

how would I go about developing a merge sort application? it cant be very hard, none of the code on other websites is long atall.

thanks :)
• ###### 6. Re: Recursive mergeSort... small problem with infinate recursion.
You will learn more if you start from the algorithm and then code it yourself.

You also might want to do non-recursive merge sort (unless using recursion is a requirement of the exercise)
• ###### 7. Re: Recursive mergeSort... small problem with infinate recursion.
How was the article on [Merge Sort|http://en.wikipedia.org/wiki/Merge_sort] on Wikipedia? Understandable?
• ###### 8. Re: Recursive mergeSort... small problem with infinate recursion.
I agree with you, but the code provided on the link I posted does compile and work well. I think you should have tested it before stating this.
• ###### 9. Re: Recursive mergeSort... small problem with infinate recursion.
im sorry, i thought i did test it...i do get an error when i try and compile it... give me a few minutes and ill come back and reply
• ###### 10. Re: Recursive mergeSort... small problem with infinate recursion.
yes sorry, that was it, when i put that code in my class... i get an acception in thread main...

heres the code i now have...

I know i need to add a main method, but im completely unsure of what I need to put inside the main method, if you get what i mean...

sorry for all the hassle... :(
``````public class part3
{

/**
* Mergesort algorithm.
* @param a an array of Comparable items.
*/
public static void mergeSort( Comparable [ ] a ) {
Comparable [ ] tmpArray = new Comparable[ a.length ];
mergeSort( a, tmpArray, 0, a.length - 1 );
}

/**
* Internal method that makes recursive calls.
* @param a an array of Comparable items.
* @param tmpArray an array to place the merged result.
* @param left the left-most index of the subarray.
* @param right the right-most index of the subarray.
*/
private static void mergeSort( Comparable [ ] a, Comparable [ ] tmpArray,
int left, int right ) {
if( left < right ) {
int center = ( left + right ) / 2;
mergeSort( a, tmpArray, left, center );
mergeSort( a, tmpArray, center + 1, right );
merge( a, tmpArray, left, center + 1, right );
}
}

/**
* Internal method that merges two sorted halves of a subarray.
* @param a an array of Comparable items.
* @param tmpArray an array to place the merged result.
* @param leftPos the left-most index of the subarray.
* @param rightPos the index of the start of the second half.
* @param rightEnd the right-most index of the subarray.
*/
private static void merge( Comparable [ ] a, Comparable [ ] tmpArray,
int leftPos, int rightPos, int rightEnd ) {
int leftEnd = rightPos - 1;
int tmpPos = leftPos;
int numElements = rightEnd - leftPos + 1;

// Main loop
while( leftPos <= leftEnd && rightPos <= rightEnd )
if( a[ leftPos ].compareTo( a[ rightPos ] ) <= 0 )
tmpArray[ tmpPos++ ] = a[ leftPos++ ];
else
tmpArray[ tmpPos++ ] = a[ rightPos++ ];

while( leftPos <= leftEnd )    // Copy rest of first half
tmpArray[ tmpPos++ ] = a[ leftPos++ ];

while( rightPos <= rightEnd )  // Copy rest of right half
tmpArray[ tmpPos++ ] = a[ rightPos++ ];

// Copy tmpArray back
for( int i = 0; i < numElements; i++, rightEnd-- )
a[ rightEnd ] = tmpArray[ rightEnd ];
}
}``````
• ###### 11. Re: Recursive mergeSort... small problem with infinate recursion.
Didn't the code you copied include a main method?
• ###### 12. Re: Recursive mergeSort... small problem with infinate recursion.
Alright, first tip: Capitalize first letter of classes Names
``````public class Part3 {
public static void main(String[] args) {
Integer[] s = { 1, 5, 3, 6, 7, 9, 2, 8, 4 }; //it could be any Comparable array
mergeSort(s);
for( int i : s )
System.out.println(i);
}
//here goes the code from java-tips
}``````
• ###### 13. Re: Recursive mergeSort... small problem with infinate recursion.
No, the code provided in [java-tips|http://www.java-tips.org/java-se-tips/java.lang/merge-sort-implementation-in-java.html] has only the merge methods.
• ###### 14. Re: Recursive mergeSort... small problem with infinate recursion.
henrique.abreu wrote:
No, the code provided in [java-tips|http://www.java-tips.org/java-se-tips/java.lang/merge-sort-implementation-in-java.html] has only the merge methods.
No wonder the OP was stuck.
1 2 Previous Next