# Counting sort (Python, functional)

Counting sort is a very simple sort that is efficient for lists that take on only a small number of values. A linear-time algorithm based on array indexing, it trades time for space.

For the purposes of this article, we'll use character elements that are restricted to integer digits, but the same ideas apply to any type. We begin by declaring a function that takes as arguments the sequence to be sorted, and the domain (in sort order) that we are sorting by.

<<counting sort>>=lambdaseq, dom: generate result

Next, we perform the sort. There are two phases to counting sort. In the first phase, *count occurrences*, we count the number of times each element of the domain occurs in the sequence. Note that we are comparing the elements of the sequence with the elements of the domain, not with each other — this is what makes counting sort not a comparison sort.

<<count occurences>>=sum(equal.outer(seq, dom))

In the second phase, *generate result*, we use `repeat`

to repeat each element of the domain as many times as we counted it in the original sequence.

<<generate result>>=repeat(dom, count occurences)

Finally we package things up with a few tests:

<<counting_sort.py>>=fromNumericimport* csort=counting sortif__name__ == "__main__":

that we expect to produce the following output:

counting sort of 3.1415926535897931 [1 1 1 2 3 3 3 4 5 5 5 6 7 8 9 9 9] counting sort of 2.71828182846 [1 1 2 2 2 4 6 7 8 8 8 8]

*this definition of counting sort may appear terse, but it is actually an expansion of the APL equivalent, in which the definition of csort would be something along the lines of *

Download code |