Consider the problem of sorting an array A[1, ..., n] of integers. We presented an O(nlogn)-time algorithm in class and, also, proved a lower bound of 2(n log n) for any comparison-based algorithm. 1. Come up with an efficient sorting algorithm for a boolean array B[1, ..., n]. 2. Come up with an efficient sorting algorithm for an array C[1, ...,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, ...,n] whose elements are distinct (D[i] # D[j], for every i / j E {1, ...,n} ) and are taken from the set {1, 2, ..., 100n}. 4. In case you designed linear-time sorting algorithms for the previous subparts, does it mean that the lower bound for sorting of (nlogn) is wrong? Explain