In-place Merge Sort – 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 “In-place Merge Sort”.

1. 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)
Explanation: In the in position merge sort, the merge function takes O(n2) time, so the recurrence relation becomes T(n)=2T(n/2)+n2. This can be solved using the master’s theorem, and the answer is O. (n2).

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. In place merge sort has same time complexity as standard merge sort.
A) true
B) false

Explanation: When compared to the regular version of merge sort, the in place version has a higher time complexity. That’s because merging in the in-place merge sort takes O(n2) time, while it takes O(n) time in the standard version.

4. In-place merge sort is a stable sort.
A) true
B) false

Explanation: In-place merge sort is a secure sort, much like regular merge sort. This means that equal-valued elements in the input and sorted arrays have the same relative location.

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

Explanation: Standard merge sort has an O(n log n) time complexity, while in-place merge sort has an O(n log n) time complexity (n2). As a result, in-place merge sort has a higher time complexity than regular merge sort.

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


Explanation: The original array is used for merging in in-place merge sort. The first elements of the two halves are compared first. If the first element of the second half is greater than the first element of the first half, we simply transfer the pointer to the first element of the first half. Otherwise, we’ll switch things to the right.

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: T(n) = 2T(n/2) + n is the recurrence relation for merge sort. This can be solved using the master’s theorem, and the answer is 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 space complexity of in place merge sort?
A) O(1)
B) O(n)
C) O(log n)
D) O(n log n)

Explanation: The in-place version of merge sort has a space complexity of O(log n), which is used to store the call stack generated by recursion. Since the value of log n is similar to 1, algorithms with a space complexity of O(log n) qualify as in place algorithms.

A sorting algorithm in which the sorted items take up the same amount of space as the unsorted items. Although these algorithms can use o(n) extra memory for bookkeeping, they only hold a fixed number of items in auxiliary memory at any given time. Sort in place is another name for it. Merge sort is a dependable sorting method. Merge sort isn’t a sorting algorithm that works in real time. The merge sort algorithm has a time complexity of (nlogn). Implement Merge Sort, which is a standard implementation that maintains the sorting algorithm. The term “in-place” refers to the fact that it does not require additional memory for the merge process, as in the regular case.

Leave a Reply

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