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

Data Structures & Algorithms Computer Science & Engineering

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

1. 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)

Explanation: The merge function in the bottom up merge sort, which is placed inside the for loop, takes O(n) time. The loop takes O(log n) time to complete, so the code’s overall time complexity is O(log n) (n log n).

2. Merge sort uses which of the following method to implement sorting?
A) merging
B) partitioning
C) selection
D) exchanging

Explanation: Merge sort is a sorting method that combines the sorted versions of smaller sections of an array. Merging is the name given to this method of sorting.

3. Bottom up merge sort uses recursion.
A) true
B) false

Explanation: The iterative method is used to implement sorting in the bottom up merge sort. It starts by combining a pair of adjacent arrays of size 1 each, then moves on to merging arrays of size 2 each, and so on.

4. Bottom up merge sort is a stable sort.
A) true
B) false

Explanation: A stable sort is a bottom up merge sort, which is similar to a regular merge sort. This means that equal-valued elements in the input and sorted arrays have the same relative location.

5. 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.

Explanation: In contrast to standard merge sort, bottom up merge sort uses an iterative algorithm to sort the data. As a result, it reduces the amount of space needed by the call stack.

6. 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);
		}
	}
}

Explanation: In order to implement sorting, the bottom up merge sort uses an iterative process. It starts by combining a pair of adjacent arrays of size 1 each, then moves on to merging arrays of size 2 each, and so on. The sorted arrays are merged in the same way that regular merge sort is done.

7. Merge sort uses which of the following algorithm to implement sorting?
A) backtracking
B) greedy algorithm
C) divide and conquer
D) dynamic programming

Explanation: To sort a given array, merge sort employs the divide-and-conquer strategy. It splits the array into two halves and applies the merge sort algorithm to each half separately before merging the sorted versions of the two halves.

8. 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)

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).

9. 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)

Explanation: The auxiliary space requirement of merge sort is O since merging two sorted arrays requires an additional space of n. (n). As a result, merge sort is not an in-place sorting method.

10. 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)

Explanation: Bottom up merge sort has the same auxiliary space complexity as regular merge sort since both use the same algorithm for merging the sorted arrays, which takes o(n) space. Bottom-up merge type, on the other hand, does not require the maintenance of a call stack.

A k-way merge sort uses repeated merges to sort a data stream. It divides the data into two streams by reading a block of data that matches in memory, sorting it, and then writing it to the next stream. The iterative merge sort algorithm will be used to sort an integer array in this article. It works by splitting a large array into two smaller subarrays and then sorting the subarrays recursively. Bottom up merge sort has the same auxiliary space complexity as regular merge sort since both use the same algorithm for merging the sorted arrays, which takes o(n) space. Bottom-up merge type, on the other hand, does not require the maintenance of a call stack.

Leave a Reply

Your email address will not be published. Required fields are marked *