Are you taking CLEP classes? Try clep.ai
| preferred AP College board partner for AP classes
AP Computer Science A/Unit 5: Writing Classes
Start Practice TestPractice Test
About Exam
hard Solved by 1 students

Merge Sort Time Complexity

Mark
< Prev
Next >

Given the MergeSort class below, and assuming the merge operation has a time complexity of O(n), what is the overall time complexity of the mergeSort method in Big-O notation?

public class MergeSort {
    public void mergeSort(int[] arr, int low, int high) {
        if(low < high) {
            int mid = (low + high) / 2;
            mergeSort(arr, low, mid);
            mergeSort(arr, mid + 1, high);
            merge(arr, low, mid, high);
        }
    }
    private void merge(int[] arr, int low, int mid, int high) {
        int n1 = mid - low + 1;
        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 + 1 + 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++];
        }
    }
}
A

O(log n)

B

O(n log n)

C

O(n^2)

D

O(n)

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

Question Leaderboard

Not enough data yet to show leaderboard.

AI Tutor

How can I help?

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