Let's break down and solve both questions step by step: --- ### **Question 5** **Given a 12-element array in descending order with distinct elements, how many comparisons are needed to apply mergesort?** - **Note:** The fact that the array is in descending order is hidden; you must apply mergesort as usual. #### **Mergesort Comparison Count:** For an array of size \( n \), mergesort's worst-case (and average-case) number of comparisons is: \[ C(n) = n \log_2 n - n + 1 \] For \( n = 12 \): \[ C(12) = 12 \log_2 12 - 12 + 1 \] \[ \log_2 12 = \log_2 (4 \times 3) = 2 + \log_2 3 \approx 2 + 1.58496 \approx 3.58496 \] \[ C(12) \approx 12 \times 3.58496 - 12 + 1 = 43.0195 - 12 + 1 = 32.0195 \] This formula is an approximation. The exact number of comparisons in mergesort for \( n \) elements is: \[ C(n) = n \lceil \log_2 n \rceil - 2^{\lceil \log_2 n \rceil} + 1 \] For \( n = 12, \lceil \log_2 12 \rceil = 4 \): \[ C(12) = 12 \times 4 - 16 + 1 = 48 - 16 + 1 = 33 \] **Final Answer:** **33 comparisons** are needed to sort a 12-element array with mergesort, regardless of initial order. --- ### **Question 14** **Given a 7-element array where \( x_1 < x_2 < x_3 \) and \( x_5 < x_6 < x_7 \), how many comparisons are needed in the worst case to sort the array?** #### **Analysis:** The array: \( \{x_1, x_2, x_3, x_4, x_5, x_6, x_7\} \) We know: - \( x_1 < x_2 < x_3 \) - \( x_5 < x_6 < x_7 \) That means we have two sorted subarrays of size 3 each and one element \( x_4 \). **To sort the entire array, we need to merge these known sequences.** #### **Step 1: Merge \( x_1, x_2, x_3 \) and \( x_5, x_6, x_7 \) with \( x_4 \)** - Consider three "blocks": A = \(x_1, x_2, x_3\), B = \(x_4\), C = \(x_5, x_6, x_7\) #### **Step 2: Lower Bound Argument** The minimal number of comparisons needed to sort n elements when you know nothing is \( \lceil \log_2 n! \rceil \). But here, since some order is known, the number of possible orderings is reduced. - Within A and C, order is fixed. - The total number of permutations = ways to interleave A, B, and C. Let’s count the number of ways to arrange these with the known constraints: - Choose 3 spots for A out of 7 positions: \( \binom{7}{3} \) - Of the remaining 4 spots, pick 3 for C: \( \binom{4}{3} \) - The last spot is for B. Total arrangements: \[ \binom{7}{3} \cdot \binom{4}{3} = 35 \times 4 = 140 \] So, the minimal number of comparisons is: \[ \lceil \log_2 140 \rceil = \lceil 7.129 \rceil = 8 \] **Final Answer:** **8 comparisons** are needed in the worst case. --- ### **Summary** - **Q5:** **33 comparisons** for mergesort on 12 elements. - **Q14:** **8 comparisons** for the worst-case, given the known order constraints on 7 elements.