CLRS 8-2 Sorting in place in linear time

Question

Suppose that we have an array of nn data records and that the key of each record has the value 0 or 1. An algorithm for sorting such a set of records might posses some subset of the following three desirable characteristics:

1. The algorithm runs in O(n)  time
2. The algorithm is stable.
3. The algorithm sorts in place, using no more than a constant amount of storage space in addition to the original array.

Do the following:

1. Give an algorithm that satisfies criteria 1 and 2 above
2. Give an algorithm that satisfies criteria 1 and 3 above
3. Give an algorithm that satisfies criteria 2 and 3 above
4. Can you use any of your algorithms from parts (a)-(c) as the sorting method used in line 2 of RADIX-SORT, so thatRADIX-SORT sorts n records with b-bit keys in  O(bn) time? Explain how or why not.
5. Suppose that the nn records have keys in the range 1
    to k
   . Show how to modify counting sort so that it sorts the records in place in O(n+k) time. You may use O(k) storage outside the input array. Is your algorithm stable? (Hint: How would you do it for k=3? )

 

 

Can somebody please provide solution with an example?