# 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.

Thanks @Gutdub for providing the solution in this issue.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 MODIFIED-COUNTING-SORT(A, k) let C[0..k] be a new array for i = 1 to k C[i] = 0 for j = 1 to A.length C[A[j]] = C[A[j]] + 1 for i = 2 to k C[i] = C[i] + C[i - 1] insert sentinel element NIL at the start of A B = C[0..k - 1] insert number 1 at the start of B // B now contains the "endpoints" for C for i = 2 to A.length while C[A[i]] != B[A[i]] key = A[i] exchange A[C[A[i]]] with A[i] while A[C[key]] == key // make sure that elements with the same keys will not be swapped C[key] = C[key] - 1 remove the sentinel element return A 

In place (storage space is $\Theta(k)$) but not stable.