Merge Sort Multiple Choice Questions and Answers (MCQs)

«
»

This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Merge Sort”.

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

Answer: c
Explanation: Merge sort uses divide and conquer in order to sort a given array. This is because it divides the array into two halves and applies merge sort algorithm to each half individually after which the two sorted halves are merged together.
advertisement

2. What is the average case time complexity of 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. It is found to be equal to O(n log n) using the master theorem.

3. What is the auxiliary space complexity of merge sort?
a) O(1)
b) O(log n)
c) O(n)
d) O(n log n)
View Answer

Answer: c
Explanation: An additional space of O(n) is required in order to merge two sorted arrays. Thus merge sort is not an in place sorting algorithm.

4. Merge sort can be implemented using O(1) auxiliary space.
a) true
b) false
View Answer

Answer: a
Explanation: Standard merge sort requires O(n) space to merge two sorted arrays. We can optimize this merging process so that it takes only constant space. This version is known as in place merge sort.

5. What is the worst case time complexity of 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 time complexity of merge sort is not affected by worst case as its algorithm has to implement the same number of steps in any case. So its time complexity remains to be O(n log n).
advertisement

6. Which of the following method is used for sorting in merge sort?
a) merging
b) partitioning
c) selection
d) exchanging
View Answer

Answer: a
Explanation: Merge sort algorithm divides the array into two halves and applies merge sort algorithm to each half individually after which the two sorted halves are merged together. Thus its method of sorting is called merging.

7. What will be the best case time complexity of 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 time complexity of merge sort is not affected in any case as its algorithm has to implement the same number of steps. So its time complexity remains to be O(n log n) even in the best case.

8. Which of the following is not a variant of merge sort?
a) in-place merge sort
b) bottom up merge sort
c) top down merge sort
d) linear merge sort
View Answer

Answer: d
Explanation: In-place, top down and bottom up merge sort are different variants of merge sort. Whereas linear merge sort is not a possible variant as it is a comparison based sort and the minimum time complexity of any comparison based sort is O(n log n).

9. Choose the incorrect statement about merge sort from the following?
a) it is a comparison based sort
b) it is an adaptive algorithm
c) it is not an in place algorithm
d) it is stable algorithm
View Answer

Answer: b
Explanation: Merge sort is not an adaptive sorting algorithm. This is because it takes O(n log n) time complexity irrespective of any case.

10. Which of the following is not in place sorting algorithm?
a) merge sort
b) quick sort
c) heap sort
d) insertion sort
View Answer

Answer: a
Explanation: An additional space of O(n) is required in order to merge two sorted arrays. Thus merge sort is not an in place sorting algorithm.
advertisement

11. Which of the following is not a stable sorting algorithm?
a) Quick sort
b) Cocktail sort
c) Bubble sort
d) Merge sort
View Answer

Answer: a
Explanation: Out of the given options quick sort is the only algorithm which is not stable. Merge sort is a stable sorting algorithm.

12. Which of the following stable sorting algorithm takes the least time when applied to an almost sorted array?
a) Quick sort
b) Insertion sort
c) Selection sort
d) Merge sort
View Answer

Answer: d
Explanation: Insertion sort takes linear time to sort a partially sorted array. Though merge and quick sort takes O(n*logn) complexity to sort, merge sort is stable. Hence, Merge sort takes less time to sort partially sorted array.

13. Merge sort is preferred for arrays over linked lists.
a) true
b) false
View Answer

Answer: b
Explanation: Merge sort is preferred for linked list over arrays. It is because in a linked list the insert operation takes only O(1) time and space which implies that we can implement merge operation in constant time.

14. Which of the following sorting algorithm makes use of merge sort?
a) tim sort
b) intro sort
c) bogo sort
d) quick sort
View Answer

Answer: a
Explanation: Tim sort is a hybrid sorting algorithm as it uses more than one sorting algorithm internally. It makes use of merge sort and insertion sort.

15. Choose the correct code for merge sort.
a)

advertisement
void merge_sort(int arr[], int left, int right) 
{ 
    if (left > right) 
    { 
 
        int mid = (right-left)/2; 
        merge_sort(arr, left, mid); 
        merge_sort(arr, mid+1, right); 
 
        merge(arr, left, mid, right); //function to merge sorted arrays
    } 
}

b)

void merge_sort(int arr[], int left, int right) 
{ 
    if (left < right) 
    { 
 
        int mid = left+(right-left)/2; 
        merge_sort(arr, left, mid); 
        merge_sort(arr, mid+1, right); 
 
        merge(arr, left, mid, right); //function to merge sorted arrays
    } 
}

c)

void merge_sort(int arr[], int left, int right) 
{ 
    if (left < right) 
    { 
 
        int mid = left+(right-left)/2; 
merge(arr, left, mid, right); //function to merge sorted arrays
        merge_sort(arr, left, mid); 
        merge_sort(arr, mid+1, right); 
 
 
    } 
}

d)

void merge_sort(int arr[], int left, int right) 
{ 
    if (left < right) 
    { 
 
        int mid = (right-left)/2; 
merge(arr, left, mid, right); //function to merge sorted arrays
        merge_sort(arr, left, mid); 
        merge_sort(arr, mid+1, right); 
 
 
    } 
}
View Answer
Answer: b
Explanation: Merge sort first sorts the two halves of the array individually. Then it merges the two sorted halves in order to obtain sorted array.
 
 

16. Which of the following sorting algorithm does not use recursion?
a) quick sort
b) merge sort
c) heap sort
d) bottom up merge sort
View Answer

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

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
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn