Recursive method in java merge sorting algorithm
I have the following merge sort code in my application. I am very confused about how the recursive method is called again after it exits the if block when the if condition fails. I have debugged my code but still don't get it. The sort method that calls mergesort (0, number-1) starts first with mergesort (0, 5). low is high, medium is 2, so nexts (0, 2) runs. This continues until we have mergesort (0, 0), in which case the low is not lower, so it exits the if block. But when I debug, the method returns and it runs again after the mergesort (0, 0) case. How will the call be repeated? Please help me. Thanks for taking the time to read my question :)
public class MergeSort {
private int[] numbers;
private int[] helper;
private int number;
public int[] sort(int[] values) {
this.numbers = values;
number = values.length;
this.helper = new int[number];
return mergesort(0, number - 1);
}
private int[] mergesort(int low, int high) {
// check if low is smaller then high, if not then the array is sorted
if (low < high) {
// Get the index of the element which is in the middle
int middle = low + (high - low) / 2;
// Sort the left side of the array
mergesort(low, middle);
// Sort the right side of the array
mergesort(middle + 1, high);
// Combine them both
merge(low, middle, high);
}
return numbers;
}
private int[] merge(int low, int middle, int high) {
// Copy both parts into the helper array
for (int i = low; i <= high; i++) {
helper[i] = numbers[i];
}
int i = low;
int j = middle + 1;
int k = low;
// Copy the smallest values from either the left or the right side back
// to the original array
while (i <= middle && j <= high) {
if (helper[i] <= helper[j]) {
numbers[k] = helper[i];
i++;
} else {
numbers[k] = helper[j];
j++;
}
k++;
}
// Copy the rest of the left side of the array into the target array
while (i <= middle) {
numbers[k] = helper[i];
k++;
i++;
}
return numbers;
}
}
+3
source to share