Question

Consider the problem of sorting an array A[1, ..., n] of integers. We presented an O(n log n)-time algorithm in class and, also, proved a lower bound of Ω(n log n) for any comparison-based algorithm.

1. Give an efficient sorting algorithm for a boolean1 array B[1, ..., n].

2. Give an efficient sorting algorithm for an array C[1,...,n] whose elements are taken from the set

{1,2,3,4,5}.

3. Give an efficient sorting algorithm for an array D[1, ..., n] whose elements are distinct (D[i] ̸= D[j],

for every i ̸= j ∈ {1, ..., n}) and are taken from the set {1, 2, ..., 2n}.

4. In case you designed linear-time sorting algorithms for the previous subparts, does it mean that

the lower bound for sorting of Ω(n log n) is wrong? Explain.

In a boolean array B[1, ..., n], each element B[i] (for i = 1, ..., n) is either 0 or 1.

Answer 1

If you have any doubts ask me ... I am happy to help u...