In-place Merge Sort Multiple choice Questions and Answers (MCQs)

YOU CAN DOWNLOAD 200+ SUBJECTS PDF BOOK FOR COMPETITIVE EXAMINATIONS

CLICK HERE TO DOWNLOAD

In-place Merge Sort Multiple choice Questions and Answers (MCQs)

Question 1 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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 apply merge sort algorithm to each half individually after which the sorted versions of these halves are merged together.

Question 2 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
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 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
What is the space complexity of in place merge sort?
A
O(1)
B
O(n)
C
O(log n)
D
O(n log n)
Question 4 Explanation: 
Space complexity of in place version of merge sort is O(log n) which is used for storing call stack formed due to recursion. Note that the algorithms with space complexity as O(log n) also qualifies as in place algorithms as the value of log n is close to 1.

Question 5 [CLICK ON ANY CHOICE TO KNOW THE RIGHT ANSWER]
What is the average time complexity of in place merge sort when we use the following function for merging?

void in....place....merge(int arr[],  int l,  int middle,  int r) { 	int start2 = middle + 1; 	if (arr[middle] <= arr[start2]) { 		return; 	} 	while (l <= middle && start2 <= r) { 		if (arr[l] <= arr[start2]) { 			l++; 		} 		else { 			int val = arr[start2]; 			int index = start2; 			while (index != l) { 				arr[index] = arr[index - 1]; 				index--; 			} 			arr[l] = val; 		 l++; 			middle++; 			start2++; 		} 	} }
A
O(n log n)
B
O(n2)
C
O(n2 log n)
D
O(n log n2)
Question 5 Explanation: 
The merge function in the in place merge sort takes O(n2) time so the recurrence relation becomes T(n)=2T(n/2)+n2. This can be solved using master's theorem and is found equal to O(n2).

There are 5 questions to complete.