Counting sort is a non-comparison-based sorting algorithm with a time complexity of $O(n+k)$, where $n$ is the number of elements to be sorted, and $k$ is the range of the input. One of the key characteristics of counting sort is that it is a stable sorting algorithm. Stability in sorting algorithms means that two records with the same key appear in the same order in the output as they do in the input. This feature is particularly important when there is additional data indexed with the elements being sorted.

How Counting Sort Works

Counting sort works by creating an auxiliary array (often called the "count array") that counts the number of occurrences of each distinct element in the input list. Once the counts are determined, it iteratively calculates the positions of each element in the sorted output.

Steps of Counting Sort:

1. Find the range of the input.
   Determine the minimum and maximum values. Suppose the smallest element is $min$ and the largest is $max$.
2. Initialize the count array.
   Create an array of size $max - min + 1$ initialized to zero.
3. Store the count of each element.
   Iterate over the input array and increment the count for each element. This places the count of each element in the position corresponding to its value.
4. Cumulative count.
   Modify the count array such that each position contains the sum of the previous counts. This step effectively transforms the count array into a prefix sum array, which gives the correct positions of elements in the sorted order.
5. Build the output array.
   Iterate over the input array again, using the count array to place each element into its correct position in the output array. Decrease the cumulative count for each element when it is placed, ensuring that the next identical element is placed in the next correct position.
6. Copy the output array back to the original array.

Stability in Counting Sort

Counting sort is stable because it processes the input array in order, and because it uses the cumulative count to position elements in the output, it naturally maintains the relative order of elements with equal keys. When the algorithm places an element from the input array into the output array, it preserves the sequential order established in the input.

Example

Consider the elements to sort: [4, 2, 2, 8, 3, 3, 1]. Each of these numbers has related data, and maintaining this relationship after sorting is important:

1. Initial input with indices:
   • 0: (4,A)
   • 1: (2,B)
   • 2: (2,C)
   • 3: (8,D)
   • 4: (3,E)
   • 5: (3,F)
   • 6: (1,G)
2. Count Array:

1. Cumulative Count Array:

1. Building the Output:

Iterate through the input array from left to right, using the cumulative count to position the elements in the output array.

• Efficiency: With $O(n+k)$ complexity, counting sort is efficient when the input keys are confined to a small range.
• Simplicity: The algorithm is straightforward to implement.
• Space: Counting sort uses auxiliary arrays whose size depends on the range of the input elements, which can become inefficient regarding space if the range is large compared to the number of elements.
• Applicability: It is best suited for sorting integers or discrete keys, limiting its use cases compared to comparison-based sorts like quicksort or mergesort.