CLRS Solutions | Problem 8-2 | Sorting in Linear Time

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:

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.

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 sorting algorithms from parts (a)-(c) as the sorting method used in line 2 of $\textsc{Radix-Sort}$, so that $\textsc{Radix-Sort}$ sorts $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 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$?)

This problem explores a fundamental tension in algorithm design. With binary keys, we can get any two of three desirable properties (linear time, stability, in-place), but achieving all three simultaneously turns out to be surprisingly difficult.

A. $O(n)$ time, stable (criteria 1 and 2)

Use $\textsc{Counting-Sort}$ with $k = 1$. Count the 0s and 1s, compute cumulative counts, then place elements into an output array by scanning backward (which preserves stability).

$$\textsc{StableBinarySort}(A, n)$$$$\begin{aligned} 1& \quad \text{let}\,C[0..1]\,\text{be}\,a\,\text{new}\,\text{array} \\ 2& \quad C[0]\,=\,0 \\ 3& \quad C[1]\,=\,0 \\ 4& \quad \textbf{for }\,j\,=\,1\textbf{ to }\,n \\ 5& \quad \qquad C[A[j].key]\,=\,C[A[j].key]\,+\,1 \\ 6& \quad C[1]\,=\,C[0]\,+\,C[1] \\ 7& \quad \text{let}\,B[1..n]\,\text{be}\,a\,\text{new}\,\text{array} \\ 8& \quad \textbf{for }\,j\,=\,n\textbf{ downto }\,1 \\ 9& \quad \qquad B[C[A[j].key]]\,=\,A[j] \\ 10& \quad \qquad C[A[j].key]\,=\,C[A[j].key]\,-\,1 \\ 11& \quad \textbf{return }\,B \\ \end{aligned}$$

This is $O(n)$ time and stable, but uses $O(n)$ extra space for the output array $B$.

B. $O(n)$ time, in-place (criteria 1 and 3)

Use a two-pointer partition similar to the one in $\textsc{Quicksort}$. One pointer advances from the left looking for 1s, the other from the right looking for 0s, and they swap when both find a misplaced element.

$$\textsc{InPlaceBinarySort}(A, n)$$$$\begin{aligned} 1& \quad i\,=\,1 \\ 2& \quad j\,=\,n \\ 3& \quad \textbf{while }\,i\,<\,j \\ 4& \quad \qquad \textbf{if }\,A[i]\,.key\,=\,0 \\ 5& \quad \qquad \qquad i\,=\,i\,+\,1 \\ 6& \quad \qquad \textbf{elseif }\,A[j]\,.key\,=\,1 \\ 7& \quad \qquad \qquad j\,=\,j\,-\,1 \\ 8& \quad \qquad \textbf{else } \\ 9& \quad \qquad \qquad \text{exchange}\,A[i]\,\text{with}\,A[j] \\ 10& \quad \qquad \qquad i\,=\,i\,+\,1 \\ 11& \quad \qquad \qquad j\,=\,j\,-\,1 \\ \end{aligned}$$

This runs in $O(n)$ time and uses $O(1)$ extra space, but is not stable because swaps can reverse the relative order of records with equal keys.

C. Stable, in-place (criteria 2 and 3)

Use $\textsc{Insertion-Sort}$. It is stable (equal elements are never swapped past each other) and in-place (only $O(1)$ extra space). However, it takes $O(n^2)$ time in the worst case, so it does not satisfy criterion 1.

D. Using in $\textsc{Radix-Sort}$

Only algorithm (a) can be used as the sorting method in $\textsc{Radix-Sort}$ because radix sort requires a stable subroutine to work correctly.

Algorithm (b) is $O(n)$ and in-place, but not stable. Using an unstable sort on individual digit positions would destroy the ordering established by previous passes, producing incorrect results.

Algorithm (c) is stable and in-place, but not $O(n)$. Using it would make radix sort $O(bn^2)$ instead of $O(bn)$.

E. In-place counting sort for keys 1 to $k$

The idea is to use the counting array to determine where each key value’s range begins, then place elements into their correct ranges using cyclic permutation. Think of it like a card-sorting game: you know how many cards belong in each pile (from the counts), so you know where each pile starts. Then for each position, if the element there belongs somewhere else, swap it to its correct pile, and keep going until the element at the current position is in the right pile.

$$\textsc{InPlaceCountingSort}(A, n, k)$$$$\begin{aligned} 1& \quad \text{let}\,C[1..k]\,\text{be}\,a\,\text{new}\,\text{array} \\ 2& \quad \textbf{for }\,i\,=\,1\textbf{ to }\,k \\ 3& \quad \qquad C[i]\,=\,0 \\ 4& \quad \textbf{for }\,j\,=\,1\textbf{ to }\,n \\ 5& \quad \qquad C[A[j]]\,=\,C[A[j]]\,+\,1 \\ 6& \quad \textbf{for }\,i\,=\,1\textbf{ to }\,k \\ 7& \quad \qquad C[i]\,=\,C[i]\,+\,C[i - 1] \\ 8& \quad \textbf{/\!/} \text{ C[i]}\,\text{ =}\,\text{ last}\,\text{ position}\,\text{ for}\,\text{ key}\,\text{ value}\,\text{ i}\, \\ 9& \quad \textbf{for }\,i\,=\,n\textbf{ downto }\,1 \\ 10& \quad \qquad \textbf{while }\,C[A[i]]\,>\,i \\ 11& \quad \qquad \qquad j\,=\,C[A[i]] \\ 12& \quad \qquad \qquad C[A[i]]\,=\,C[A[i]]\,-\,1 \\ 13& \quad \qquad \qquad \text{exchange}\,A[i]\,\text{with}\,A[j] \\ 14& \quad \qquad C[A[i]]\,=\,C[A[i]]\,-\,1 \\ \end{aligned}$$

The counting phase takes $\Theta(n + k)$ time and $O(k)$ space. In the placement phase, each exchange moves at least one element to its final position, so the total number of exchanges across all iterations is at most $n$. The overall running time is $O(n + k)$.

This algorithm is not stable. The cyclic swapping disrupts the relative order of records with equal keys. For example, with $k = 3$ and values $\langle 2_a, 1, 2_b, 3 \rangle$, the in-place permutation may output $2_b$ before $2_a$.

Problem 8-2

A. \(O(n)\) time, stable (criteria 1 and 2)

B. \(O(n)\) time, in-place (criteria 1 and 3)

C. Stable, in-place (criteria 2 and 3)

D. Using in \(\textsc{Radix-Sort}\)

E. In-place counting sort for keys 1 to \(k\)