CountingSort

Last edit September 9, 2005

An algorithm for stable sorting integers in linear time. Count how many of each value appear in the set, then place each value according to how many of them there are.

If, like CeeLanguage, the ProgrammingLanguage supports only arrays with indices >= 0, the numbers to be sorted must be limited to non-negative integers and the complexity is O(n+k), where k is the maximum integer in the unsorted array plus 1.

Sample code in PythonLanguage:

 def counting(alist):
     length = len(alist)
     if not length: return
     if min(alist) < 0: raise ValueError('integer values must be >= 0')
     counts = [0] * (max(alist)+1)
     for val in alist: counts[val] += 1
     for i in xrange(1, len(counts)): counts[i] += counts[i-1]   # running total
     results = [0] * length
     for i in xrange(length-1, -1, -1):   # loop backwards for stable sort
         val = alist[i]
         counts[val] -= 1
         results[ counts[val] ] = val
     alist[:] = results

CountingSort can, I think, be performed on sets of integers with negative values in languages, such as JavaScript and FortranLanguage, which support negative array indices. I should try coding this up in JavaScript to verify the previous sentence. -- ElizabethWiethoff

Or simply use the minimum that you've already computed and subtract that from every value in the counting phase, giving values from zero onwards.

Calling this "CountingSort" doesn't ring a bell offhand, do I just have a mental block? You're clearly describing basically the simplest variant of RadixSort. -- DougMerritt

Well, it's presented separately from RadixSort in my book and has nothing to do with the powers of whatever root. You count how many of each value appear in the set, then place each value according to how many of them there are. I'll come up with a larger treatment tomorrow or the day after. Right now I have to help my friend finally do his income tax returns. Feh. -- Eliz

My sympathies, I'll be patient. (P.S. good for you to help the poor procrastinator, that's a great kindness. :-) When you return, do please note which book you're talking about, and also note I don't know what "powers of whatever root" has to do with this, and also that your phrase about placement by cardinality confuses me, since that's not what I thought you were saying above. Thanks, -- Doug

Meanwhile, a quick search finds:

It is in fact a kind of RadixSort, and apparently CountingSort is a well-known name for this variant. I guess I do have a mental block on the name.

MasteringAlgorithmsWithCee (OreillyAndAssociates) is the book.

CategoryAlgorithm SortingAlgorithms