Complete for homework, due Monday, 3 June 2002.
Taken from Introduction to Algorithms,
T. H. Corman, C. E. Leiserson, R. L. Rivest, p. 184.
9-2 Sorting in place in linear time
- Suppose that we have an array of n data records
to sort and that the key of each record has the value 0 or 1.
Give a simple linear-time algorithm for sorting the n
data records in place. Use no storage of more than constant
size in addition to the storage provided by the array.
- Can your sort from the previous part be used to radix sort
n records with b-bit keys in O(bn) time?
Explain how or why not.
- Suppose that the n records have keys in the range from
1 to k. Show how to modify counting sort so that the records
can be sorted in place in O(n+k) time. You may use O(k)
storage outside the input array. ( Hint: How would you
do it for k=3 )