Sort an array A. of N integers in between 1 and K.
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.
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
||Max = 100
||Max = 1000
||Max = 40000
||Max = 99999
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
Reordering of input array such that
COUNTING_SORT: procedure expose A.
parse arg N, K
C. = 0
do J = 1 to N
Aj = A.J; C.Aj = C.Aj + 1
do J = 2 to K
Jm1 = J - 1; C.J = C.J + C.Jm1
do J = N to 1 by -1
Aj = A.J; CAj = C.Aj; B.CAj = A.J
C.Aj = CAj - 1
do J = 1 to N; A.J = B.J; end
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms
The MIT Press, Cambridge, 1990
Sedgewick R., Algorithms
Addison-Wesley, Reading, Massachusetts, 1984
I changed the test from Max=10 ... 40000
to Max=100 ... 99999
. Thanks for idea go to Walter Pachl.
This test ran in the Windows 2000 Professional environment on the computer with 132MB RAM and processor x86Family 6 Mode 6 Stepping 5.