Q.1 What is the main idea behind Merge Sort?
Divide and conquer
Dynamic programming
Greedy approach
Backtracking
Explanation - Merge Sort uses divide and conquer by recursively splitting the array into halves and then merging them in sorted order.
Correct answer is: Divide and conquer
Q.2 What is the worst-case time complexity of Merge Sort?
O(n)
O(n log n)
O(n^2)
O(log n)
Explanation - Regardless of input, Merge Sort divides into halves and merges, leading to O(n log n) complexity.
Correct answer is: O(n log n)
Q.3 Which data structure is heavily used in Merge Sort?
Stack
Queue
Array
Graph
Explanation - Merge Sort generally relies on arrays for splitting and merging operations.
Correct answer is: Array
Q.4 What is the best-case time complexity of Merge Sort?
O(n log n)
O(n^2)
O(n)
O(log n)
Explanation - Unlike some algorithms, Merge Sort does not improve in the best case; it always requires O(n log n).
Correct answer is: O(n log n)
Q.5 Is Merge Sort a stable sorting algorithm?
Yes
No
Depends on implementation
Only for linked lists
Explanation - Merge Sort preserves the relative order of equal elements, making it stable.
Correct answer is: Yes
Q.6 Which type of algorithm is Merge Sort?
In-place and stable
Not in-place but stable
In-place and unstable
Not in-place and unstable
Explanation - Merge Sort requires extra memory for merging, so it is not in-place but it is stable.
Correct answer is: Not in-place but stable
Q.7 What is the space complexity of Merge Sort?
O(1)
O(log n)
O(n)
O(n log n)
Explanation - Merge Sort requires O(n) additional space for temporary arrays during merging.
Correct answer is: O(n)
Q.8 Which problem-solving strategy does Merge Sort use?
Greedy
Dynamic Programming
Divide and Conquer
Brute Force
Explanation - Merge Sort splits the problem into smaller subproblems and then merges the solutions.
Correct answer is: Divide and Conquer
Q.9 Which of the following sorting algorithms guarantees O(n log n) complexity?
Bubble Sort
Insertion Sort
Merge Sort
Selection Sort
Explanation - Merge Sort guarantees O(n log n) in all cases, unlike others which may degrade.
Correct answer is: Merge Sort
Q.10 What happens during the merge step of Merge Sort?
Two unsorted lists are concatenated
Two sorted lists are combined into a single sorted list
Array is divided into halves
Elements are swapped randomly
Explanation - In the merge step, two sorted halves are merged into one sorted array.
Correct answer is: Two sorted lists are combined into a single sorted list
Q.11 Which scenario is best suited for Merge Sort?
Sorting small arrays
Sorting linked lists
Sorting when memory is limited
Sorting nearly sorted arrays
Explanation - Merge Sort works efficiently with linked lists because merging can be done without extra space.
Correct answer is: Sorting linked lists
Q.12 What is the time complexity of merging two sorted arrays of size m and n?
O(m + n)
O(mn)
O(log m + log n)
O(max(m, n))
Explanation - Merging requires scanning all elements of both arrays once, so O(m+n).
Correct answer is: O(m + n)
Q.13 Which is true about Merge Sort compared to Quick Sort?
Merge Sort is faster in practice
Merge Sort has better worst-case complexity
Quick Sort is always stable
Quick Sort uses more memory
Explanation - Merge Sort guarantees O(n log n) worst case, while Quick Sort can degrade to O(n^2).
Correct answer is: Merge Sort has better worst-case complexity
Q.14 Which kind of recursion does Merge Sort use?
Tail recursion
Head recursion
Mutual recursion
Nested recursion
Explanation - Merge Sort splits and recursively sorts before merging, so recursive calls occur before processing.
Correct answer is: Head recursion
Q.15 How many subarrays are created in Merge Sort at the deepest level?
n
log n
n/2
2n
Explanation - At the deepest level, each element is a subarray of size 1, so n subarrays are created.
Correct answer is: n
Q.16 Merge Sort is preferred for external sorting because:
It has less time complexity
It is stable and sequential
It requires no extra space
It is in-place
Explanation - Merge Sort processes data sequentially, making it efficient for large external data.
Correct answer is: It is stable and sequential
Q.17 Which operation dominates the runtime of Merge Sort?
Division of array
Merging sorted arrays
Swapping elements
Recursive calls
Explanation - Most work in Merge Sort happens during the merge step, which combines elements.
Correct answer is: Merging sorted arrays
Q.18 If an array of size 8 is sorted using Merge Sort, how many levels of splitting occur?
2
3
4
8
Explanation - Array of size 8 is split log2(8) = 3 times before reaching single elements.
Correct answer is: 3
Q.19 Which sorting technique is often implemented with parallel algorithms?
Merge Sort
Bubble Sort
Selection Sort
Insertion Sort
Explanation - Merge Sort’s divide and merge steps are suitable for parallelization.
Correct answer is: Merge Sort
Q.20 Which is more space efficient: Merge Sort on arrays or linked lists?
Arrays
Linked lists
Both same
Depends on data size
Explanation - Merge Sort on linked lists can be done with constant space, unlike arrays which need O(n).
Correct answer is: Linked lists
Q.21 How many comparisons are made in merging two arrays of size n each?
n
2n
n log n
Up to 2n - 1
Explanation - In the worst case, every comparison is needed until one array is exhausted.
Correct answer is: Up to 2n - 1
Q.22 Which phase of Merge Sort ensures sorted order?
Splitting phase
Merging phase
Recursive calls
Initialization phase
Explanation - The merging phase ensures that smaller sorted arrays combine into a sorted result.
Correct answer is: Merging phase
Q.23 How many times is the array split during Merge Sort for n elements?
n times
log n times
n log n times
n/2 times
Explanation - The array is halved until single elements remain, so log n levels of splitting occur.
Correct answer is: log n times
Q.24 Which of the following is NOT true about Merge Sort?
It is stable
It is recursive
It sorts in O(n log n)
It requires no extra memory
Explanation - Merge Sort needs O(n) auxiliary space for temporary arrays.
Correct answer is: It requires no extra memory
Q.25 Merge Sort is efficient for:
Large datasets
Small datasets
Datasets with few duplicates
Datasets with random distribution
Explanation - Merge Sort’s O(n log n) efficiency and stability make it suitable for large datasets.
Correct answer is: Large datasets