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

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.

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

Question Leaderboard

Rank
User
Correct Count
Attempt Count
Time
Score
#1upadhgau00002 0m 00s -20
#2ethan12 2m 14s -44
#3theofanusmischa01 0m 46s -56
#4richa.tuli11 4m 00s -140
#5suhanakochhar00613 3m 56s -156
Items per page:
10
1 – 5 of 5
No comments yet. Be the first to comment!

AI Tutor

How can I help?

APFIVE © 2020.
Email: apfive@apfive.org|Privacy Policy