Virtual Labs

1. What is the complexity of merging two subarrays in the merge sort algorithm? Assume the sizes to be M and N.

a: O(M + N) Explanation

Explanation

b: O(M * N) Explanation

Explanation

c: O(M * N^2) Explanation

Explanation

d: O((M * N) ^ 2) Explanation

Explanation

2. Which of the following algorithms perform better than merge sort in the worst case time complexity?

a: Heap Sort Explanation

Explanation

b: Quick Sort Explanation

Explanation

c: Both a and b Explanation

Explanation

d: None of the above Explanation

Explanation

3. In merge sort, what is the time complexity of finding the midpoint of the current subarray to determine where it should be divided?

a: O(1) Explanation

Explanation

b: O(N) Explanation

Explanation

c: O(N log N) Explanation

Explanation

d: O(N^2) Explanation

Explanation

4. What will be the maximum possible array size at the ith level of the merge sort tree for an array of size N (assume level indexing starts from 0, i.e, the original array at the root is said to be at the 0th level)? Fractional results will be rounded up to the nearest integer.

a: 2^i * N Explanation

Explanation

b: i * N Explanation

Explanation

c: N / i Explanation

Explanation

d: N / 2^i Explanation

Explanation

5. What is the main purpose of the merge operation in merge sort?

a: To combine two sorted subarrays into one sorted subarray Explanation

Explanation

b: To randomly rearrange the elements of an array Explanation

Explanation

c: To divide an array into two smaller arrays Explanation

Explanation

d: To remove duplicate elements from an array Explanation

Explanation

6. What happens to the size of each subarray when merge sort divides an array into two approximately equal parts?

a: It approximately doubles. Explanation

Explanation

b: It remains unchanged. Explanation

Explanation

c: It is approximately halved. Explanation

Explanation

d: It becomes zero. Explanation

Explanation

7. Which of the following is the base case for recursively dividing an array in merge sort?

a: An array containing

N/2

elements Explanation

Explanation

b: An empty or one-element array Explanation

Explanation

c: An array containing

N

elements Explanation

Explanation

d: An array containing exactly two elements Explanation

Explanation

8. If two sorted subarrays contain

M

and

N

elements, respectively, how many elements must be processed in total to produce their merged result?

M \times N

Explanation

M + N

Explanation

M^2 + N^2

Explanation

\log(M + N)

Explanation

9. Which statement best explains why the total merging work at one level of the merge sort tree is

O(N)

for an array containing

N

elements?

a: Only one element is processed at each level. Explanation

Explanation

b: Every pair of elements is compared with each other. Explanation

Explanation

c: The number of subarrays becomes

N^2

at every level. Explanation

Explanation

d: Across all merges at that level, each element is processed a constant number of times. Explanation

Explanation

Merge Sort