250+ TOP MCQs on In-place Merge Sort and Answers

Data Structures & Algorithms Multiple Choice Questions on “In-place Merge Sort”.

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

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

2. What is the average case time complexity of standard merge sort?
a) O(n log n)
b) O(n²)
c) O(n² log n)
d) O(n log n²)
View Answer

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

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

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

5. 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(n²)
c) O(n² log n)
d) O(n log n²)
View Answer

Answer: b
Clarification: The merge function in the in place merge sort takes O(n²) time so the recurrence relation becomes T(n)=2T(n/2)+n². This can be solved using master’s theorem and is found equal to O(n²).

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

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

7. In place merge sort has same time complexity as standard merge sort.
a) true
b) false

Answer: b
Clarification: In place version of merge sort has a greater time complexity as compared to its standard version. It is because the merging in in-place merge sort takes place in O(n²) time whereas in standard version it takes O(n) time.

8. In-place merge sort is a stable sort.
a) true
b) false

Answer: a
Clarification: In-place 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 incorrect statement about merge sort from the following?
a) both standard merge sort and in-place merge sort are stable
b) standard merge sort has greater time complexity than in-place merge sort
c) standard merge sort has greater space complexity than in-place merge sort
d) in place merge sort has O(log n) space complexity

Answer: b
Clarification: Time complexity of standard merge sort is O(n log n) and that of in-place merge sort is O(n²). So the time complexity of in-place merge sort is more than that of standard merge sort.

10. Choose the correct function from the following that implements merging in in-place merge sort.
a)

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+1 && 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++; 
		} 
	} 
}

b)

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++; 
		} 
	} 
}

c)

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+1 && 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++; 
		} 
	} 
}

d)

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 != r) 
                        { 
				arr[index] = arr[index - 1]; 
				Index++; 
			} 
			arr[l] = val; 
		        l++; 
			middle++; 
			start2++; 
		} 
	} 
}

View Answer

Answer: b
Clarification: Merging in in-place merge sort takes place in the original array itself. We first compare the first elements of the two halves. If the first element of second half is greater then we just increment the pointer of the first element of first half. Otherwise we shift elements to the right.

and Answers.