## Introduction

Counting sort is an algorithm generally used for sorting smaller integers. It is able to sort integer input in linear time and is ideal for situations where a large number of integer keys need to be sorted. For smaller sets, a comparison sort is probably more appropriate. It is best used when the integer keys are not larger than the number of items in the set and is thus, frequently combined with radix sort, which allows for larger input keys.

## Background

Based on Introduction to Algorithms Third Edition p. 195.

Counting sort assumes that each of the n input elements is an integer in the range 0 to k, for some integer k. When k=O(n), the sort runs in theta(n) time. Counting sort determines, for each input element x, the number of elements less than x. It uses this information to place element x directly into its position in the output array. For example, if 17 elements are less than x, then x belongs in output position 18.

**CONFUSING NOTE**: This algorithm assumes that the C array starts at index 0 and

the A array starts at index 1. This had to be accounted for in the actual code.

I did this by making the bounds of some of the loops go from 0 to k inclusive

and by subtracting 1 in from the array index of B in line 11 of the algorithm.

COUNTING-SORT(A, B, k)
1) let C[0..k] b. a new array<<br mode="hold" />2) for i=0 to k do
3) C[i] = 0
4) for j to length[A] do
5) C [ A[ j ]] C [ A[ j ]] + 1
6)
7) for i = 1 to k do
8) C[i] = C[i] + C[i − 1]
9)
10) for j length[A] down to 1 do
11) B[C[A[j]]] = A[j]
12) C[A[j]] = C[A[j]] − 1

## Using the Code

To use the code in your own program, copy and paste the count sort function below into your code. The code is designed to be modular. It takes as input the array to be sorted and a value `k`

, which represents the largest value in the array.

int *countSort(int arrayA[], int k) {
int arrayA_length = sizeof(arrayA);
int * arrayB = (int *)malloc(arrayA_length * sizeof(int));
int * arrayC = (int *)malloc((k+1) * sizeof(int));
for(int i = 0; i <= k; i++)
arrayC[i] = 0;
for(int j = 0; j < arrayA_length; j++)
arrayC[arrayA[j]] = arrayC[arrayA[j]] + 1;
for(int i = 1; i <= k; i++)
arrayC[i] = arrayC[i] + arrayC[i-1];
for(int j = arrayA_length - 1; j >= 0; j--) {
arrayB[arrayC[arrayA[j]] - 1] = arrayA[j];
arrayC[arrayA[j]] = arrayC[arrayA[j]] - 1;
}
for(int i = 0; i < sizeof(arrayA); i++)
arrayA[i] = arrayB[i];
free(arrayB);
free(arrayC);
return arrayA;
}
...