.

# Counting Sort Algorithm Assignment Help

Counting sort assumes which each one of the n input elements is an integer within the range 1 to k, for some integer k. Whenever k = O(n), the sort runs within linear time.

Fundamental concept: determine, for every input element x, the number of elements less than x. This enables one to determine x’s position in the sorted array.

## The code makes use of the following arrays:

- A[1..n] is the input array, with length[A] = n.
- B[1..n] holds the sorted output.
- C[1..k] provides temporary storage.

### Example for Counting sort:

Fig : The operation of COUNTING_SORT on an input array A[1..8], where each element of A is positive integer no larger than k = 6.

- The array A and the auxiliary array C after line 4.
- The array C after line 7
- The output array B and the auxiliary array C after one, two and three iterations of the loop in line 9-11 respectively. Only the lightly shaded elements of array B have been filled in.
- The final sorted output array B.

.