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
Sorting Problem
Heapsort
Shellsort
Quicksort
Merging

Literature
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms
The MIT Press, Cambridge, 1990
Sedgewick R., Algorithms