| preferred AP College board partner for AP classes
AP Computer Science A/Unit 10: Recursion
Start Practice Test
Share
hard Solved by 7 students
Merge Sort Recursive Call Indices
< Prev
Next >

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.

Hint
Did You Know?
Explain Why
Explain All Answers
Check Answer
Show Correct Answer

Question Leaderboard

Rank
User
Correct Count
Attempt Count
Time
Score
#1upadhgau00002 0m 00s -20
#2ethan12 2m 14s -44
#3richa.tuli11 4m 00s -140
#4suhanakochhar00613 3m 56s -156
APFIVE © 2020.
Email: [email protected]|Privacy Policy