## Two Linear Sorts

### November 13, 2009

Count sort runs in four loops. The first loop counts the number of elements equal to *i*, storing the counts in the *s* array. The second loop sums the counts to compute the number of elements less than or equal to each *i*. The third loop builds the output, and the fourth loop copies the output back to the input.

`function sort(A,n, i,s,t) {`

for (i = 0; i <= n; i++) ++s[A[i]]

for (i = 1; i <= n; i++) s[i] += s[i-1]

for (i = n; i >= 0; i--) t[s[A[i]]--] = A[i]

for (i = 0; i <= n; i++) A[i] = t[i] }

Count sort is repeated inline in radix sort; variable *p* counts the digit positions from right to left:

`function digit(x,k) {`

while (k-- > 0)

x = int(x / 10)

return x % 10 }

`function sort(A,n, b,m,p,i,s,t) {`

for (m = 1; m <= n; m *= 10) b++

for (p = 0; p < b; p++) {

for (i = 0; i < 10; i++)

s[i] = 0

for (i = 1; i <= n; i++)

s[digit(A[i], p)]++

for (i = 1; i < 10; i++)

s[i] += s[i-1]

for (i = n; i >= 1; i--) {

t[s[digit(A[i], p)]] = A[i]

s[digit(A[i], p)]-- }

for (i = 1; i <= n; i++)

A[i] = t[i] } }

Our radix sort used count sort on decimal digits. But there is no requirement to use decimal digits; some count sorts use binary bits, and you might consider choosing the greatest integer less than or equal to the square root of *n* as the radix. And any other sorting method may be used in place of count sort, as long as it is stable.

The code is collected at http://programmingpraxis.codepad.org/YMEdwxX5, but you can’t run it because codepad doesn’t provide an Awk interpreter.

my implementation for count sort in c

forget to free count array. Add given code after line 32

My implementation of radix list sort in C