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:

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

Do the following:

- Give an algorithm that satisfies criteria 1 and 2 above
- Give an algorithm that satisfies criteria 1 and 3 above
- Give an algorithm that satisfies criteria 2 and 3 above
- Can you use any of your algorithms from parts (a)-(c) as the sorting method used in line 2 of
`RADIX-SORT`

, so that`RADIX-SORT`

sorts n records with b-bit keys in O(bn) time? Explain how or why not.
- 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?