Definition: counting sort

A sorting technique that is used when the range of keys is relatively small and there are duplicate keys. Counting sorts differ from sorts that compare data in multiple passes. They work by creating an array of counters the size of the largest integer in the list; therefore, the keys must be integers or data that can be readily converted to integers.

In the first pass, each key value is used to index into the array to add 1. For example, if the key field contains 0000123, the 123rd counter in the array is incremented by 1.

Counting Sort vs. Rapid Sort
Space equal to the original unordered list is allocated in memory, and the second pass of the counting sort scans the original list and uses the data in the counters to move each record from the original list into the sorted list.

A "rapid sort" is similar to a counting sort, except that it is used to only count the number of occurrences of key fields with no additional data. Instead of using the data in the counters to move records into a new sequence, the counter data in a rapid sort are used to print each key field along with its corresponding count. See sort algorithm.

A Counter Array

The array contains a counter for each key value. For example, if they range from 1 to 1,000 there would be 1,000 counters. In the final pass, the counter data is used to move the unsorted records to a new sorted order (counting sort) or to print the number of occurrences of just the key (rapid sort).