Counting Sort in PHP: Implementation, Steps, Advantages, and Use Cases

In PHP development, sorting algorithms are essential for handling data, and choosing an efficient one is crucial when dealing with large datasets.

1. Introduction to Counting Sort

Counting sort is a non‑comparison integer sorting algorithm that counts the occurrences of each value to determine positions, achieving O(n + k) time complexity where n is the array length and k is the range of values.

2. Steps of Counting Sort

Find the maximum and minimum values to determine the range.

Count the occurrences of each element using a count array.

Accumulate the count array to obtain the final positions.

Traverse the original array in reverse, placing each element into the sorted array based on the accumulated counts.

3. PHP Implementation

The following PHP code demonstrates the counting sort algorithm:

function countingSort(array $arr): array {
    $max = max($arr);
    $min = min($arr);
    $range = $max - $min + 1;

    // 初始化计数数组
    $count = array_fill(0, $range, 0);

    // 统计每个元素出现的次数
    foreach ($arr as $num) {
        $count[$num - $min]++;
    }

    // 累加计数数组
    for ($i = 1; $i < $range; $i++) {
        $count[$i] += $count[$i - 1];
    }

    // 反向填充目标数组
    $sortedArr = array_fill(0, count($arr), 0);
    for ($i = count($arr) - 1; $i >= 0; $i--) {
        $sortedArr[--$count[$arr[$i] - $min]] = $arr[$i];
    }

    return $sortedArr;
}

// 示例
$arr = [5, 3, 1, 2, 4, 5, 2];
$sortedArr = countingSort($arr);
print_r($sortedArr);

4. Advantages and Disadvantages

Advantages

Low time complexity: O(n) when k = O(n), outperforming comparison sorts.

Stability: maintains the relative order of equal elements.

Disadvantages

High space complexity: requires O(n + k) extra memory.

Limited applicability: works only for integers and can be memory‑intensive when the range k is large.

5. Application Scenarios

Small value range where k ≪ n.

When a stable sort is required.

Sorting non‑negative integers (negative numbers can be handled with an offset).

6. Conclusion

Counting sort is a simple and efficient algorithm for sorting integers within a limited range, and it can be a powerful tool in PHP projects that need fast, stable sorting for suitable data sets.