# 8-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$. An algorithm for sorting such a set of records might possess 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.

a. Give an algorithm that satisfies criteria 1 and 2 above.

b. Give an algorithm that satisfies criteria 1 and 3 above.

c. Give an algorithm that satisfies criteria 2 and 3 above.

d. Can you use any of your sorting algorithms from parts (a)–(c) as the sorting method used in line 2 of $\text{RADIX-SORT}$, so that $\text{RADIX-SORT}$ sorts $n$ records with $b$-bit keys in $O(bn)$ time? Explain how or why not.

e. Suppose that the $n$ records have keys in the range from $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? ($\textit{Hint:}$ How would you do it for $k = 3$?)

a. Counting-Sort.

b. Quicksort-Partition.

c. Insertion-Sort.

d. (a) Yes. (b) No. (c) No.

e. Using $O(k)$ outside the input-arr.

  1 2 3 4 5 6 7 8 9 10 11 COUNTING-SORT(A, k) let C[0..k] be a new array for i = 0 to k C[i] = 0 for i = 1 to A.length C[A[i]] = C[A[i]] + 1 // C[i] now contains the number of elements equal to i p = 0 for i = 0 to k for j = 1 to C[i] p = p + 1 A[p] = i 

Not stable, in place, in $O(n + k)$.