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