Counting Sort

function countingSort(arr) {
    // Find the range of input values
    const max = Math.max(...arr);
    const min = Math.min(...arr);
    const range = max - min + 1;

    // Initialize count array
    const count = new Array(range).fill(0);
    const output = new Array(arr.length);

    // Count frequency of each element
    for (let i = 0; i < arr.length; i++) {
        count[arr[i] - min]++;
    }

    // Cumulative count
    for (let i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // Build output array
    for (let i = arr.length - 1; i >= 0; i--) {
        output[count[arr[i] - min] - 1] = arr[i];
        count[arr[i] - min]--;
    }

    // Copy sorted elements back to original array
    for (let i = 0; i < arr.length; i++) {
        arr[i] = output[i];
    }

    return arr;
}

How Counting Sort Works

Counting Sort operates by counting the frequency of each distinct element in the input, then using this frequency information to determine the correct position of each element in the sorted output array.

Algorithm Steps:

1. Find Range: Determine the minimum and maximum values in the array
2. Initialize Count Array: Create array sized to the range of input values
3. Count Frequencies: Count how many times each value appears
4. Cumulative Sum: Convert counts to cumulative positions
5. Build Output: Place elements in correct sorted positions
6. Copy Back: Transfer sorted elements to original array

Key Characteristics:

• Stable: Maintains relative order of equal elements
• Not In-place: Requires additional space O(n + k)
• Non-comparison: Doesn't compare elements directly
• Linear Time: O(n + k) when range k is reasonable

Advantages:

• Linear time complexity: O(n + k) for small ranges
• Stable sorting: Preserves order of equal elements
• Simple implementation: Easy to understand and code
• Predictable performance: No worst-case scenarios

When to Use Counting Sort:

• Small range: When the range of values (k) is much smaller than n
• Integers only: Works best with positive integer inputs
• Linear time needed: When O(n log n) comparison sorts are too slow
• Stability required: When equal elements must maintain order

Limitations:

• Large ranges: Becomes inefficient when k >> n
• Non-integers: Doesn't work directly with floating-point numbers
• Memory usage: Requires O(n + k) additional space
• Negative numbers: Needs modification to handle negative values