Merge Sort

1. What is the space complexity of the merge sort algorithm?

a: O(N) Explanation

Explanation

b: O(2^N) Explanation

Explanation

c: O(1) Explanation

Explanation

d: O(N^2) Explanation

Explanation

2. Consider the array: A = [8, 7, -2, 4, 1, 100, 0, -1]. Which of the following pairs of subarrays are merged together at some point during merge sort (assume ascending order)?

a: [-2, 4] and [1, 100] Explanation

Explanation

b: [7, 8] and [-2, 4] Explanation

Explanation

c: [8, 7] and [-2, 4] Explanation

Explanation

d: [1, 4] and [0, 100] Explanation

Explanation

3. Why is the time complexity of merge sort O(N log N)?

a: N for dividing the array and log(N) for the number of division steps. Explanation

Explanation

b: N for merging subarrays and log(N) for the number of merge steps. Explanation

Explanation

c: N for the number of division steps and log(N) for dividing the array. Explanation

Explanation

d: N for the number of merge steps and log(N) for merging subarrays. Explanation

Explanation

4. Consider the array: A = [0, -1, 100, 110, 1, 5]. Which of the following shows the correct steps in sorting this array using merge sort?

a: [0, -1, 100, 110, 1, 5] → [0, -1, 100], [110, 1, 5] → [0], [-1, 100], [110], [1, 5] → [0], [-1], [100], [110], [1], [5] → [-1, 0], [100], [1, 110], [5] → [-1, 0, 100], [1, 5, 110] → [-1, 0, 1, 5, 100, 110] Explanation

Explanation

b: [0, -1, 100, 110, 1, 5] → [0, -1, 100], [110, 1, 5] → [0, -1], [100], [110, 1], [5] → [0], [-1], [100], [110], [1], [5] → [0], [-1, 100], [110], [1, 5] → [-1, 0, 100], [1, 5, 110] → [-1, 0, 1, 5, 100, 110] Explanation

Explanation

c: [0, -1, 100, 110, 1, 5] → [0, -1, 100], [110, 1, 5] → [0], [-1, 100], [110], [1, 5] → [0], [-1], [100], [110], [1], [5] → [0], [-1, 100], [110], [1, 5] → [-1, 0, 100], [1, 5, 110] → [-1, 0, 1, 5, 100, 110] Explanation

Explanation

d: [0, -1, 100, 110, 1, 5] → [0, -1, 100], [110, 1, 5] → [0], [-1, 100], [110, 1], [5] → [0], [-1], [100], [110], [1], [5] → [0], [-1, 100], [1, 110], [5] → [-1, 0, 100], [1, 5, 110] → [-1, 0, 1, 5, 100, 110] Explanation

Explanation

5. When merging two sorted subarrays in ascending order, which element should normally be selected next?

a: The larger of the first remaining elements Explanation

Explanation

b: The smaller of the first remaining elements Explanation

Explanation

c: The element from the longer subarray Explanation

Explanation

d: The element from the subarray containing fewer elements Explanation

Explanation

6. If an array contains

8

elements, how many splitting levels are required to reach subarrays containing one element?

a: 2 Explanation

Explanation

b: 3 Explanation

Explanation

c: 4 Explanation

Explanation

d: 8 Explanation

Explanation

7. Which recurrence most accurately represents the time complexity of merge sort for

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. Which property can make a standard merge sort implementation stable?

a: Choosing the left subarray's element first when two compared keys are equal Explanation

Explanation

b: Randomly selecting between equal elements Explanation

Explanation

c: Reversing the order of equal elements during every merge Explanation

Explanation

d: Removing duplicate elements before merging Explanation

Explanation

9. Why does merge sort have approximately

\log_2 N

levels of division for

N

elements?

a: Each level approximately doubles the number of elements in the original array. Explanation

Explanation

b: Each level removes one element from the array. Explanation

Explanation

c: Each level performs

N

comparisons. Explanation

Explanation

d: Each level approximately halves the size of every active subarray. Explanation

Explanation