(Solved): Problem 2 (Sorting special arrays) 20 Consider the problem of sorting an array \( A[1, \ldots, n] ...

Problem 2 (Sorting special arrays) 20 Consider the problem of sorting an array \( A[1, \ldots, n] \) of integers. We presented an \( O(n \log n) \)-time algorithm in class and, also, proved a lower bound of \( \Omega(n \log n) \) for any comparison-based algorithm. 1. Come up with an efficient sorting algorithm for a boolean \( { }^{1} \) array \( B[1, \ldots, n] \). 2. Come up with an efficient sorting algorithm for an array \( C[1, \ldots, n] \) whose elements are taken from the set \( \{1,2,3,4,5,6,7,8,9,10\} \). 3. Come up with an efficient sorting algorithm for an array \( D[1, \ldots, n] \) whose elements are distinct \( (D[i] \neq D[j] \), for every \( i \neq j \in\{1, \ldots, n\}) \) and are taken from the set \( \{1,2, \ldots, 100 n\} \). 4. In case you designed linear-time sorting algorithms for the previous subparts, does it mean that the lower bound for sorting of \( \Omega(n \log n) \) is wrong? Explain.