Counting Sort

Counting sort is a non-comparative sorting algorithm that sorts integers by counting the number of occurrences of each unique element in the array. It then uses this information to place each element in its correct sorted position.

Algorithm Overview

Counting sort works by determining, for each input element, the number of elements that are less than it. This information allows the algorithm to place each element directly into its correct position in the output array.

Key Features

Non-Comparative: Doesn't compare elements directly
Stable: Maintains relative order of equal elements
Linear Time: O(n + k) where k is the range of input values
Integer-Specific: Works with non-negative integers (or known ranges)
Multiple Variants: Several implementations for different use cases

Time and Space Complexity

Time Complexity: O(n + k) where n is number of elements, k is range
Space Complexity: O(k) for counting array + O(n) for output = O(n + k)
When k = O(n): Effectively O(n) - linear time sorting!
When k >> n: Performance degrades, other algorithms may be better

Algorithm Steps

Find the range of input values (0 to max_value or custom range)
Create a count array to store frequency of each value
Count occurrences of each element
Calculate cumulative counts for stable positioning
Build output array by placing elements in correct positions
Process from right to left to maintain stability

Usage Examples

Basic Usage

from algo.algorithms.sorting.counting_sort import counting_sort

# Sort integers
numbers = [4, 2, 2, 8, 3, 3, 1]
sorted_numbers = counting_sort(numbers)
print(sorted_numbers)  # [1, 2, 2, 3, 3, 4, 8]

# With known maximum value (optimization)
result = counting_sort([1, 4, 1, 2, 7, 5, 2], max_val=7)
print(result)  # [1, 1, 2, 2, 4, 5, 7]

# Empty array
result = counting_sort([])
print(result)  # []

In-Place Sorting

from algo.algorithms.sorting.counting_sort import counting_sort_in_place

# Modify original array
arr = [3, 1, 4, 1, 5]
counting_sort_in_place(arr)
print(arr)  # [1, 1, 3, 4, 5]

Handling Negative Numbers

from algo.algorithms.sorting.counting_sort import counting_sort_with_range, counting_sort_auto_range

# With known range
result = counting_sort_with_range([-5, 3, -1, 0, 8], -5, 8)
print(result)  # [-5, -1, 0, 3, 8]

# Automatically determine range
numbers = [-2, 1, -1, 0, 2]
sorted_numbers = counting_sort_auto_range(numbers)
print(sorted_numbers)  # [-2, -1, 0, 1, 2]

Educational/Debugging

from algo.algorithms.sorting.counting_sort import counting_sort_verbose

# See step-by-step process
counting_sort_verbose([4, 2, 2, 8, 3])

Output:

Starting counting sort on: [4, 2, 2, 8, 3]
Maximum value in array: 8
Created count array of size 9: [0, 0, 0, 0, 0, 0, 0, 0, 0]
After counting occurrences: [0, 0, 2, 1, 1, 0, 0, 0, 1]
Count array breakdown:
  Value 2 appears 2 time(s)
  Value 3 appears 1 time(s)
  Value 4 appears 1 time(s)
  Value 8 appears 1 time(s)

Calculating cumulative counts:
  count[2] = 2 + 0 = 2
  count[3] = 1 + 2 = 3
  count[4] = 1 + 3 = 4
  count[8] = 1 + 4 = 5
Cumulative count array: [0, 0, 2, 3, 4, 0, 0, 0, 5]

Building output array (processing from right to left for stability):
  Place 3 at position 2, decrement count[3] to 2
  Place 8 at position 4, decrement count[8] to 4
  Place 2 at position 1, decrement count[2] to 1
  Place 2 at position 0, decrement count[2] to 0
  Place 4 at position 3, decrement count[4] to 3

Final sorted array: [2, 2, 3, 4, 8]

Suitability Analysis

from algo.algorithms.sorting.counting_sort import is_suitable_for_counting_sort, counting_sort_get_stats

# Check if counting sort is efficient for your data
data = [1, 2, 3, 4, 5]
suitable = is_suitable_for_counting_sort(data)
print(f"Suitable: {suitable}")  # True

# Get detailed statistics
sorted_data, stats = counting_sort_get_stats(data)
print(f"Range size: {stats['range_size']}")
print(f"Space efficiency: {stats['space_efficiency']:.2f}")

Optimized Usage

from algo.algorithms.sorting.counting_sort import counting_sort_optimized

# Automatically chooses best algorithm
data = [1, 1000000]  # Large range - will fall back to comparison sort
result = counting_sort_optimized(data)
print(result)  # [1, 1000000]

Edge Cases Handled

# Empty array
result = counting_sort([])  # Returns []

# Single element
result = counting_sort([42])  # Returns [42]

# All same elements
result = counting_sort([5, 5, 5, 5])  # Returns [5, 5, 5, 5]

# Large range (falls back to comparison sort in optimized version)
try:
    result = counting_sort([1, 1000000])  # Works but inefficient
except ValueError:
    pass  # Or use counting_sort_optimized instead

# Negative numbers (basic version raises error)
try:
    counting_sort([-1, 2, 3])
except ValueError as e:
    print(e)  # "Counting sort only works with non-negative integers"

API Reference

Counting Sort Algorithm Implementation

Counting sort is a non-comparative sorting algorithm that sorts integers by counting the number of occurrences of each unique element in the array. It then uses this information to place each element in its correct sorted position.

Time Complexity: O(n + k) where n is the number of elements and k is the range of input

Space Complexity: O(k) for the counting array plus O(n) for output array = O(n + k)

Stability: Stable (maintains relative order of equal elements)

Note: Only works with non-negative integers or integers within a known range

`counting_sort(arr, max_val=None)`

Sort an array of non-negative integers using the counting sort algorithm.

The algorithm works by: 1. Finding the maximum value in the array (or using provided max_val) 2. Creating a count array to store frequency of each element 3. Calculating cumulative counts to determine positions 4. Building the output array by placing elements in correct positions

Parameters:

Name	Type	Description	Default
`arr`	`List[int]`	List of non-negative integers to sort	required
`max_val`	`Optional[int]`	Optional maximum value in the array (for optimization)	`None`

Returns:

Type	Description
`List[int]`	A new sorted list (does not modify the original array)

Raises:

Type	Description
`ValueError`	If the array contains negative numbers

Examples:

>>> counting_sort([4, 2, 2, 8, 3, 3, 1])
[1, 2, 2, 3, 3, 4, 8]

>>> counting_sort([1, 4, 1, 2, 7, 5, 2])
[1, 1, 2, 2, 4, 5, 7]

>>> counting_sort([])
[]

`counting_sort_auto_range(arr)`

Counting sort that automatically determines the range from the input array.

This version can handle negative numbers by automatically finding min and max values.

Parameters:

Name	Type	Description	Default
`arr`	`List[int]`	List of integers to sort	required

Returns:

Type	Description
`List[int]`	A new sorted list

Examples:

>>> counting_sort_auto_range([-5, 3, -1, 0, 8, -2])
[-5, -2, -1, 0, 3, 8]

`counting_sort_get_stats(arr)`

Counting sort that returns both the sorted array and statistics about the sort.

Parameters:

Name	Type	Description	Default
`arr`	`List[int]`	List of non-negative integers to sort	required

Returns:

Type	Description
`List[int]`	A tuple containing:
`dict`	The sorted array
`Tuple[List[int], dict]`	A dictionary with statistics (max_val, range_size, unique_count)

Raises:

Type	Description
`ValueError`	If the array contains negative numbers

`counting_sort_in_place(arr, max_val=None)`

In-place counting sort implementation.

This version modifies the original array instead of creating a new one. Uses less memory but destroys the original array.

Parameters:

Name	Type	Description	Default
`arr`	`List[int]`	List of non-negative integers to sort	required
`max_val`	`Optional[int]`	Maximum value in the array (computed if not provided)	`None`

Returns:

Type	Description
`List[int]`	The sorted list (same object as input, modified in-place)

Raises:

Type	Description
`ValueError`	If the array contains negative numbers

`counting_sort_optimized(arr)`

Optimized version that decides whether to use counting sort or fall back to comparison sort.

Parameters:

Name	Type	Description	Default
`arr`	`List[int]`	List of integers to sort	required

Returns:

Type	Description
`List[int]`	A new sorted list

`counting_sort_verbose(arr, max_val=None)`

Counting sort with detailed step-by-step output for educational purposes.

This version prints each step of the sorting process to help understand how the algorithm works.

Parameters:

Name	Type	Description	Default
`arr`	`List[int]`	List of non-negative integers to sort	required
`max_val`	`Optional[int]`	Optional maximum value in the array	`None`

Returns:

Type	Description
`List[int]`	A new sorted list

Raises:

Type	Description
`ValueError`	If the array contains negative numbers

`counting_sort_with_range(arr, min_val, max_val)`

Counting sort that works with integers in a specific range [min_val, max_val].

This version can handle negative numbers by shifting the range.

Parameters:

Name	Type	Description	Default
`arr`	`List[int]`	List of integers to sort (must be within [min_val, max_val])	required
`min_val`	`int`	Minimum value in the expected range	required
`max_val`	`int`	Maximum value in the expected range	required

Returns:

Type	Description
`List[int]`	A new sorted list

Raises:

Type	Description
`ValueError`	If any element is outside the specified range

Examples:

>>> counting_sort_with_range([-2, 1, -1, 0, 2], -2, 2)
[-2, -1, 0, 1, 2]

`is_suitable_for_counting_sort(arr, threshold=0.5)`

Determine if counting sort is suitable for the given array.

Counting sort is most efficient when the range of values (k) is not significantly larger than the number of elements (n). This function helps decide whether counting sort is a good choice.

Parameters:

Name	Type	Description	Default
`arr`	`List[int]`	List of integers to analyze	required
`threshold`	`float`	Minimum space efficiency ratio (n/k) to consider suitable	`0.5`

Returns:

Type	Description
`bool`	True if counting sort is recommended, False otherwise

Examples:

>>> is_suitable_for_counting_sort([1, 2, 3, 4, 5])  # Good case
True
>>> is_suitable_for_counting_sort([1, 1000000])  # Bad case
False