Virtual Labs

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

Merge Sort