Counting sort
PROBLEM
Sort an array A. of N integers in between 1 and K.
ALGORITHM
Counting sort, or distribution counting, was invented by Harold H. Seward in 1954. Counting sort assumes that each of the N input elements is an integer in the range 1 to K. When K=O(N), the sort runs in O(N) time. This algorithm uses a temporary array.
PRACTICE
The following table compares four sorting algorithms. The A. array includes integers in the range 1 to Max=10,100,1000,40000.
Running time in seconds for N=10000 

Algorithm 
Max = 100 
Max = 1000 
Max = 40000 
Max = 99999 
QUICKSORT 
4.66 
4.53 
4.89 
4.59 
HEAPSORT 
10.26 
10.67 
11.58 
11.18 
SHELLSORT 
7.45 
8.89 
10.58 
10.13 
COUNTING_SORT 
1.88 
1.95 
7.93 
31.85 
IMPLEMENTATION
Unit: nonrecursive internal subroutine
Global variables: the input array A. of an integer in the range 1 to K
Parameters: a positive integer N  number of elements in A., a positive integer K
Result:
Reordering of input array such that A.1<=A.2<=...<=A.N
COUNTING_SORT: procedure expose A.
parse arg N, K
C. = 0
do J = 1 to N
Aj = A.J; C.Aj = C.Aj + 1
end
do J = 2 to K
Jm1 = J  1; C.J = C.J + C.Jm1
end
do J = N to 1 by 1
Aj = A.J; CAj = C.Aj; B.CAj = A.J
C.Aj = CAj  1
end
do J = 1 to N; A.J = B.J; end
return

CONNECTIONS
Literature Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms The MIT Press, Cambridge, 1990
Sedgewick R., Algorithms AddisonWesley, Reading, Massachusetts, 1984
Acknowledgement I changed the test from Max=10 ... 40000 to Max=100 ... 99999. Thanks for idea go to Walter Pachl.
Note This test ran in the Windows 2000 Professional environment on the computer with 132MB RAM and processor x86Family 6 Mode 6 Stepping 5.
