Merge Sort

1. Consider the array: A = [9, 100, -1, 4, 8, 6, 9]. How many rounds of splitting (dividing) and how many total split operations are needed to break the array down for merge sort? (A round means all splits at the same level; a split operation means each time an array is divided.)

a: 2 rounds, 6 splits Explanation

Explanation

b: 3 rounds, 6 splits Explanation

Explanation

c: 6 rounds, 2 splits Explanation

Explanation

d: 6 splits, 3 rounds Explanation

Explanation

2. During which step of merge sort does the actual sorting happen?

a: Splitting (division) Explanation

Explanation

b: A separate sorting step Explanation

Explanation

c: Merging Explanation

Explanation

d: None of the above Explanation

Explanation

3. Which of the following best describes how the merge step works in merge sort (for ascending order)?

a: We just join the subarrays one after the other. Explanation

Explanation

b: We compare the first elements of each subarray, add the smaller one to the result, and repeat until all elements are merged. Explanation

Explanation

c: We alternate picking elements from each subarray regardless of value. Explanation

Explanation

d: None of the above. Explanation

Explanation

4. What is the first major operation performed by merge sort on an unsorted array?

a: Divide the array into smaller subarrays Explanation

Explanation

b: Find the largest element Explanation

Explanation

c: Reverse the array Explanation

Explanation

d: Remove duplicate elements Explanation

Explanation

5. If the two sorted subarrays [1, 4, 7] and [2, 3, 8] are merged in ascending order, what is the resulting array?

a: [2, 3, 1, 4, 7, 8] Explanation

Explanation

b: [1, 4, 7, 2, 3, 8] Explanation

Explanation

c: [1, 2, 3, 4, 7, 8] Explanation

Explanation

d: [8, 7, 4, 3, 2, 1] Explanation

Explanation

6. Why can a one-element subarray be considered sorted in merge sort?

a: It contains the largest possible value. Explanation

Explanation

b: There is no pair of elements within it that can be out of order. Explanation

Explanation

c: It has already been compared with every other element. Explanation

Explanation

d: It does not need to be stored in memory. Explanation

Explanation

7. Which recurrence represents the running time of merge sort on an array of

N

elements?

T(N)=T(N-1)+O(1)

Explanation

T(N)=T(N/2)+O(N)

Explanation

T(N)=2T(N/2)+O(N)

Explanation

T(N)=2T(N-1)+O(1)

Explanation

8. Why does merge sort have

O(N\log N)

time complexity even in the worst case?

a: It performs only one comparison for the entire input. Explanation

Explanation

b: It divides the array into a logarithmic number of levels and performs linear total merging work at each level. Explanation

Explanation

c: It always removes half of the elements after every comparison. Explanation

Explanation

d: It uses constant space during every merge. Explanation

Explanation

9. Which statement about the merge phase of merge sort is correct when merging two sorted subarrays?

a: Every element in the first subarray must be compared with every element in the second subarray. Explanation

Explanation

b: The two subarrays must first be shuffled randomly. Explanation

Explanation

c: The merge operation can use the sorted order of the two subarrays to process their elements efficiently. Explanation

Explanation

d: The merge operation ignores the values of the elements. Explanation

Explanation