# Merge Sort – Multiple Choice Questions and Answers (MCQs)

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

1. Which of the following method is used for sorting in merge sort?
A) merging
B) partitioning
C) selection
D) exchanging

Explanation: The merge sort algorithm splits the array into two halves and applies the merge sort algorithm to each half separately before merging the two sorted halves. Merging is the name given to this method of sorting.

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

Explanation: Merge sort’s time complexity is unaffected in any case since its algorithm must follow the same number of steps. Even in the best case, the time complexity remains O(n log n).

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

Explanation: Merge sort is divided into three types: in-place, top down, and bottom up. Linear merge sort, on the other hand, is not a viable option since it is a comparison-based sort, and any comparison-based sort has a minimum time complexity of O. (n log n).

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

Explanation: Merge sort is not a sorting algorithm that adapts to the situation. This is due to the fact that it has a time complexity of O(n log n) in all cases.

5. Which of the following is not in place sorting algorithm by default?
A) merge sort
B) quick sort
C) heap sort
D) insertion sort

Explanation: Fast sort, heap sort, and insertion sort are in-place sorting algorithms, while merging two sorted arrays requires an additional space of O(n). We have a merge sort variant (to do in-place sorting), but it is not the default option. As a result, merge sort is the best option among the available options.

6. Which of the following is not a stable sorting algorithm?
A) Quick sort
B) Cocktail sort
C) Bubble sort
D) Merge sort

Explanation: The only algorithm that isn’t stable among the options is fast type. Merge sort is a dependable sorting method.

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

Explanation: Sorting a partially sorted array with insertion sort takes linear time. Merge sort is stable, even though merge and fast sort have O(n*logn) complexity. As a result, Merge sort saves time when sorting a partially sorted list.

8. Merge sort is preferred for arrays over linked lists.
A) true
B) false

Explanation: For linked lists, merge sort is favoured over arrays. Since the insert operation in a linked list takes only O(1) time and space, we can implement the merge operation in constant time.

9. Which of the following sorting algorithm makes use of merge sort?
A) tim sort
B) intro sort
C) bogo sort
D) quick sort

Explanation: Tim sort is a hybrid sorting algorithm since it employs many sorting algorithms. Merge sort and insertion sort are employed.

10. Choose the correct code for merge sort.
A)

```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);

}
}```

Explanation: Merge sort sorts the two halves of the collection separately first. The two sorted halves are then combined to create a sorted list.

11. Which of the following sorting algorithm does not use recursion?
A) quick sort
B) merge sort
C) heap sort
D) bottom up merge sort

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.

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

Explanation: To sort a given array, merge sort employs divide and conquer. This is because it splits the array into two halves and applies the merge sort algorithm to each half separately before merging the two sorted halves.

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

Explanation: T(n) = 2T(n/2) + n is the recurrence relation for merge sort. Using the master theorem, it is found to be O(n log n).

14. What is the auxiliary space complexity of merge sort?
A) O(1)
B) O(log n)
C) O(n)
D) O(n log n)

Explanation:
To merge two sorted arrays, an additional space of O(n) is needed. As a result, merge sort is not an in-place sorting method.

15. Merge sort can be implemented using O(1) auxiliary space.
A) true
B) false

Explanation: To merge two sorted arrays, a standard merge sort needs O(n) space. We should make this merger process take up as little space as possible. In position merge sort is the name for this version.

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

Explanation: Merge sort’s time complexity is unaffected by the worst case since its algorithm must implement the same number of steps in all cases. As a result, its time complexity remains O. (n log n).

Merge sort (also known as mergesort) is a general-purpose, comparison-based sorting algorithm developed in computer science. The majority of implementations result in a stable sort, which means that the order of equivalent elements in the input and output is the same. In 1945, John von Neumann invented the merge sort algorithm, which is a divide and conquer algorithm. Goldstine and von Neumann published a study in 1948 that included a thorough summary and analysis of bottom-up merge sort. Example C-like code for a top-down merge sort algorithm that recursively splits the list into sublists until the sublist size reaches 1, then merges the sublists to generate a sorted list using indices.