Merge Sort Recursive Call Indices
Why does this mergeSort implementation use mergeSort(arr, low, mid) and mergeSort(arr, mid, high) instead of mid+1 in the second recursive call?
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 the implementation uses an exclusive high index, so arr[low…mid-1] and arr[mid…high-1] represent the correct subarrays.
B
Because the merge method is designed to handle overlapping subarrays when using inclusive indices.
C
Because using mid+1 would result in missing the middle element of the array, causing an array index out of bounds error.
D
Because mergeSort always expects the second recursive call to include the mid index for proper pivot selection.
Question Leaderboard
| Rank | |||||
|---|---|---|---|---|---|
| #1 | upadhgau000 | 0 | 2 | 0m 00s | -20 |
| #2 | ethan | 1 | 2 | 2m 14s | -44 |
| #3 | richa.tuli | 1 | 1 | 4m 00s | -140 |
| #4 | suhanakochhar006 | 1 | 3 | 3m 56s | -156 |
APFIVE