Bottom-Up Mergesort Multiple Choice Questions and Answers (MCQs)

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Bottom-Up Mergesort”.

1. Merge sort uses which of the following algorithm to implement sorting?
a) backtracking
b) greedy algorithm
c) divide and conquer
d) dynamic programming
View Answer

Answer: c
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.

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)
View Answer

Answer: a
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).

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)
View Answer

Answer: c
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.
advertisement
advertisement

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)
View Answer

Answer: b
Explanation: The auxiliary space complexity of bottom up merge sort is same as standard merge sort as both uses the same algorithm for merging the sorted arrays which takes o(n) space. But bottom up merge sort does not need to maintain a call stack.

5. What is the average time complexity of bottom up merge sort?
a) O(n log n)
b) O(n2)
c) O(n2 log n)
d) O(n log n2)
View Answer

Answer: a
Explanation: The merge function in the bottom up merge sort takes O(n) time which is placed inside the for loop. The loop runs for O(log n) time, thus the overall time complexity of the code becomes O(n log n).
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. Merge sort uses which of the following method to implement sorting?
a) merging
b) partitioning
c) selection
d) exchanging
View Answer

Answer: a
Explanation: Merge sort implements sorting by merging the sorted versions of smaller parts of the array. Thus its method of sorting is called merging.

7. Bottom up merge sort uses recursion.
a) true
b) false
View Answer

Answer: b
Explanation: Bottom up merge sort uses the iterative method in order to implement sorting. It begins by merging a pair of adjacent array of size 1 each and then merge arrays of size 2 each in the next step and so on.
advertisement

8. Bottom up merge sort is a stable sort.
a) true
b) false
View Answer

Answer: a
Explanation: Bottom up merge sort like standard merge sort is a stable sort. This implies that the relative position of equal valued elements in the input and sorted array remain same.

9. Choose the correct statement about bottom up merge sort from the following?
a) bottom up merge sort has greater time complexity than standard merge sort
b) bottom up merge sort has lesser time complexity than standard merge sort
c) bottom up merge sort saves auxiliary space required on call stack
d) bottom up merge sort uses recursion.
View Answer

Answer: c
Explanation: Bottom up merge sort unlike standard merge sort uses an iterative algorithm for sorting. Thus, it saves auxiliary space required by the call stack.
advertisement

10. Choose the correct option from the following that represents bottom up merge sort function?
a)

void mergesort(int Arr[], int temp[], int low, int high)
{	
	for (int m = 1; m <= high - low; m = 2*m)
	{	
		for (int i = low; i < high; i += 2*m)
		{
			int left = i;
			int mid = i + m - 1;
			int right = min(i + 2*m - 1, high);		
			merge(Arr, temp, left, mid, right);
		}
	}
}

b)

void mergesort(int Arr[], int temp[], int low, int high)
{	
	for (int m = 1; m <= high - low; m = 2*m)
	{	
		for (int i = low; i < high; i += m)
		{
			int left = i;
			int mid = i + m - 1;
			int right = min(i + 2*m - 1, high);
			merge(Arr, temp, left, mid, right);
		}
	}
}

c)

void mergesort(int Arr[], int temp[], int low, int high)
{	
	for (int m = 1; m <= high - low; m = m)
	{	
		for (int i = low; i < high; i += 2*m)
		{
			int left = i;
			int mid = i + m - 1;
			int right = min(i + 2*m - 1, high);
			merge(Arr, temp, left, mid, right);
		}
	}
}

d)

void mergesort(int Arr[], int temp[], int low, int high)
{	
	for (int m = 1; m <= high - low; m = 2*m)
	{	
		for (int i = low; i < high; i += 2*m)
		{
			int left = i;
			int mid = i + m - 1;
			int right = min(i + m - 1, high);
			merge(Arr, temp, left, mid, right);
		}
	}
}
View Answer
Answer: a
Explanation: Bottom up merge sort uses iterative method in order to implement sorting. It begins by merging a pair of adjacent array of size 1 each and then merge arrays of size 2 each in the next step and so on. The process of merging the sorted arrays is same as in standard merge sort.
 
 

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.