# Bottom-Up Mergesort Multiple choice Questions and Answers (MCQs)

## Bottom-Up Mergesort Multiple choice Questions and Answers (MCQs)

 Question 1
Merge sort uses which of the following algorithm to implement sorting?
 A backtracking B greedy algorithm C divide and conquer D dynamic programming
Question 1 Explanation:
Merge sort uses the technique of divide and conquer in order to sort a given array. It divides the array into two halves and applies merge sort algorithm to each half individually after which the sorted versions of these halves are merged together.

 Question 2
What is the average case time complexity of standard merge sort?
 A O(n log n) B O(n2) C O(n2 log n) D O(n log n2)
Question 2 Explanation:
The recurrence relation for merge sort is given by T(n) = 2T(n/2) + n. This can be solved using master's theorem and is found equal to O(n log n).

 Question 3
What is the auxiliary space complexity of standard merge sort?
 A O(1) B O(log n) C O(n) D O(n log n)
Question 3 Explanation:
The merging of two sorted arrays requires an additional space of n due to which the auxiliary space requirement of merge sort is O(n). Thus merge sort is not an in place sorting algorithm.

 Question 4
What is the auxiliary space complexity of bottom up merge sort?
 A O(1) B O(n) C O(log n) D O(n log n)