## Sorting without comparisons: Counting Sort

Suppose I have an array of $n$ numbers, each of which is in
the range $0,\ldots,k-1$. For this discussion, we'll take $k$
to be less than $n$, though that's not strictly necessary, and
we'll think of these $k$ values as categories.

Algorithm: Counting Sort(A,n,k)
Inputs: A,n,k where A is an array of n values in the range 0..k-1
Output: B an array containing the elements of A in sorted order (least to greatest)
// count the number of occurences of each value, i.e. C[i] = the number of i's in A
C = an array of n zeros
for i from 0 to n-1 do
C[A[i]]++
// set elements of C s.t. C[i] is the number of values in A that are ≤ i
for i from 1 to k-1 do
C[i] += C[i-1]
// place each element of A into B in its sorted-order position
B = an empty array of size n
for i from n-1 down to 0 do
C[i]--
B[C[i]] = A[i]
return B

This clearly runs in linear time! So have we proved that our
"proof" of the $\Omega(n \lg n)$ worst-case bound on sorting
was a lie?!?!?! No! This sorting algorithm is not based on
comparisons, so that result doesn't apply.

Counting Sort does apply more generally than just to
integers. Any categorical data that we can give integer
labels to (e.g. characters) works. Moreover, often we are
sorting large objects, but using some integer value as a
"key" for sorting purposes (e.g. sorting mids by alpha
code). In project 2, we saw a nice example of this. There we
objects that consisted of row,col positions. We (or at
least I) wanted to sort these objects by column value.
Counting Sort allows us to do this sorting in time linear in
$\max(n,k)$, which for this discussion is just
$\Theta(n)$.