| 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 2 students
Merge Sort Time Complexity
< Prev
Next >

Assuming that the merge operation takes O(n) time, what is the overall time complexity in Big-O notation of the ‘mergeSort’ method?

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(n log n)

B

O(n^2)

C

O(log n)

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.

No comments yet. Be the first to comment!

AI Tutor

How can I help?

APFIVE © 2020.
Email: [email protected]|Privacy Policy