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)$.