Merge Sort Recursive Call Indices
In the provided mergeSort implementation, the recursive calls are mergeSort(arr, low, mid) and mergeSort(arr, mid, high). Why is mid used as the starting index for the second recursive call instead of mid + 1?
public class MergeSortDebug {
public static void mergeSort(int[] arr, int low, int high) {
if(low < high) {
int mid = (low + high) / 2;
mergeSort(arr, low, mid);
mergeSort(arr, mid, high);
merge(arr, low, mid, high);
}
}
public static void merge(int[] arr, int low, int mid, int high) {
int n1 = mid - low;
int n2 = high - mid;
int[] left = new int[n1];
int[] right = new int[n2];
for(int i = 0; i < n1; i++)
left[i] = arr[low + i];
for(int j = 0; j < n2; j++)
right[j] = arr[mid + j];
int i = 0, j = 0, k = low;
while(i < n1 && j < n2) {
if(left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while(i < n1)
arr[k++] = left[i++];
while(j < n2)
arr[k++] = right[j++];
}
public static void main(String[] args) {
int[] data = {4, 2, 7, 1};
mergeSort(data, 0, data.length);
for(int num : data)
System.out.print(num + " ");
}
}
A
Because using mid+1 would result in missing the middle element of the array, causing an array index out of bounds error.
B
Because the merge method is designed to handle overlapping subarrays when using inclusive indices.
C
Because mergeSort always expects the second recursive call to include the mid index for proper pivot selection.
D
Because the implementation uses an exclusive high index, so arr[low…mid-1] and arr[mid…high-1] represent the correct subarrays.
Question Leaderboard
| Rank | |||||
|---|---|---|---|---|---|
| #1 | upadhgau000 | 0 | 2 | 0m 00s | -20 |
| #2 | ethan | 1 | 2 | 2m 14s | -44 |
| #3 | theofanusmischa | 0 | 1 | 0m 46s | -56 |
| #4 | richa.tuli | 1 | 1 | 4m 00s | -140 |
| #5 | suhanakochhar006 | 1 | 3 | 3m 56s | -156 |
Items per page:
10
1 – 5 of 5
APFIVE