Stack overflow from a missed function call
I'm sorry if this is posted elsewhere (I can't find anything since my problem is pretty specific), but I understand (or at least theoretically) what the error is; I'm having trouble figuring out how to fix this. The code should show how merge sort works; The code works, but it never makes a call to the "merge" function (code below, I know it is bad practice to call everything in imports, but this is not a large project, so I don't care; just a preview, but it's written import java.util .; and imports java.security .;).
import java.util.*;
import java.security.*;
public class Merge {
public static void mergeSort(int[] data) {
sortArray(data, 0, data.length - 1);
}
private static void sortArray(int[] data, int low, int high) {
if ((high - low) >= 1) {
int m1 = low + high;
int m2 = m1 + 1;
System.out.printf("Split: %s\n", subarrayString(data, low, high));
System.out.printf(" %s\n", subarrayString(data, low, m1));
System.out.printf(" %s\n\n", subarrayString(data, m2, high));
sortArray(data, low, m1);
sortArray(data, m2, high);
merge(data, low, m1, m2, high);
}
}
public static void merge(int[] data, int l, int m1, int m2, int r) {
int lIndex = l, rIndex = r, cIndex = l, combined[] = new int[data.length];
System.out.printf("Merge: %s\n", subarrayString(data, l, m1));
System.out.printf(" %s\n", subarrayString(data, m1, r));
while (lIndex <= data[rIndex]) {
if (data[lIndex] <= data[rIndex])
combined[cIndex++] = data[lIndex++];
else
combined[cIndex++] = data[rIndex++];
}
if (lIndex == m2)
while (rIndex <= r) combined[cIndex++] = data[rIndex++];
else
while (lIndex <= m1) combined[cIndex++] = data[rIndex++];
}
private static String subarrayString(int[] data, int low, int high) {
StringBuilder temp = new StringBuilder();
for (int i = 0; i < low; i++)
temp.append(" ");
for (int i = 0; i < high; i++)
temp.append(" " + data[i]);
return temp.toString();
}
public static void main2() {
SecureRandom gen = new SecureRandom();
int[] data = new int[10];
for (int i = 0; i < data.length; i++) data[i] = 10 + gen.nextInt(50);
System.out.printf("\nUnsorted Array:\n%s\n\n", Arrays.toString(data));
mergeSort(data);
System.out.printf("\nSorted Array:\n%s\n\n", Arrays.toString(data));
}
}
Let me know if you need a driver file. To recap, the problem is that it never reaches the merge function call and results in an error.
source to share
A common cause is a bad recursive call. Typically, this is caused when your recursive functions do not have a correct termination condition. In your code, the 1st recursive call is always called with the same parameter 0 and (length - 1) and no interruption, and it will get stuck in an infinite loop. Correct your code and update the value of m1 to terminate.
Consider array length 6:
low = 0 and high = 5 m1 = 5 sortArray(data, 0, 5);
source to share