I'm doing a school project where I have to write a program that performs a merge sort. The mergeSort() method is recursive and is causing a stack overflow error. I know that this happens if a recursive method continues endlessly, but I can't figure out what in my code is making it not stop.
Any help would be greatly appreciated.
Here is the code (it's run with a Sort.java program provided by my professor, if that clarifies why there is no main method):
public class Merge {
/**
* Sort an array, in-place, using merging.
* @param array The array to be sorted.
* POSTCONDITION: The elements of array are in ascending order.
*/
public static void sort(int[] array) {
int[] tempArray = mergeSort(array);
for (int i = 0; i < tempArray.length; i++) {
array[i] = tempArray[i];
}
}
/**
* Extract the portion of an array from start up to (excluding) stop.
* @param array The source array.
* @param start The starting index (inclusive).
* @param stop The ending index (exclusive).
* @return An array containing the same elements the portion of array.
* PRECONDITION: 0 <= start <= stop <= array.length
*/
private static int[] subarray(int[] array, int start, int stop) {
int[] newArray = new int[stop-start];
for (int i = 0; i < newArray.length; i++) {
newArray[i] = array[start + i];
}
return newArray;
}
/**
* Merge two sorted arrays into one new array.
* @param first The first array, already sorted.
* @param second The second array, already sorted.
* @return A new array containing the elements of first and second,
* in order.
*/
private static int[] merge(int[] first, int[] second) {
int[] newArray = new int[first.length + second.length];
int count = 0;
int i = 0;
int j = 0;
while ((i < first.length) || (j < second.length)) {
if ((i < first.length) && (j < second.length)) {
if (first[i] < second[j]) {
newArray[count++] = first[i++];
} else {
newArray[count++] = second[j++];
}
} else if (j < second.length) {
newArray[count++] = second[j++];
} else if (i < first.length) {
newArray[count++] = first[i++];
}
}
return newArray;
}
/**
* Sort an array by merging.
* @param array The array to sort.
* @return A new array containing the elements of array, in order.
*/
private static int[] mergeSort(int[] array) {
int split = 0;
if (array.length < 2) {
return array;
} else {
split = array.length%2;
int[] array1 = mergeSort(subarray(array, 0, split));
int[] array2 = mergeSort(subarray(array, split, array.length));
return merge(array1, array2);
}
}
}
split = array.length%2;butsplit = array.length/2;as pointed out by a user who just deleted his comment.