Counting Sort Algorithm

Counting sort is a sorting algorithm that sorts the elements of an array by counting the number of occurrences of each unique element in the array. The count is stored in an auxiliary array and the sorting is done by mapping the count as an index of the auxiliary array.

Working of Counting Sort

Input Array Example:
[4, 2, 2, 8, 3, 3, 1]

Step 1: Find the Maximum Value

• Find the largest number in the array.
• In this example, the maximum = 8.

Step 2: Create Count Array

• Make a count array of size (max + 1) → here size = 9.
• Initialize all values to 0.
  count [] = [0, 0, 0, 0, 0, 0, 0, 0, 0]

Step 3: Count Each Element

• For each element in the input array, increase its value’s count.
• Input: [4, 2, 2, 8, 3, 3, 1]
• Count becomes: [0, 1, 2, 2, 1, 0, 0, 0, 1]

Step 4: Cumulative Sum

• Modify the count array to store cumulative counts.
• Cumulative Count: [0, 1, 3, 5, 6, 6, 6, 6, 7]
• This tells us the position of each number in the final sorted array.

Step 5: Build Output Array

• Create an output array.
• Traverse input array from right to left and place each element in the correct position using count [].

Output: [1, 2, 2, 3, 3, 4, 8]

 Step 6: Copy to Original Array (Optional)

• Copy the sorted values from output array to original array if required.

 Final Sorted Array:

• [1, 2, 2, 3, 3, 4, 8]

Counting sort python code:

function countingSort(arr):

    maxVal = max(arr)

    count = [0] * (maxVal + 1)

    for num in arr:

        count[num] += 1

    for i = 1 to maxVal:

        count[i] += count[i – 1]

    for i from len(arr)-1 to 0:

        output[count[arr[i]] – 1] = arr[i]

        count[arr[i]] -= 1

Time Complexity of Counting Sort