PHP Radix Sort Algorithm
last modified April 16, 2025
Basic Definitions
An algorithm is a step-by-step procedure to solve a problem or perform a computation. Sorting algorithms arrange elements in a specific order.
Common sorting algorithms include bubble sort, selection sort, insertion sort, merge sort, quick sort, heap sort, and radix sort. Each has different time and space complexity characteristics.
Radix Sort Overview
Radix sort is a non-comparative integer sorting algorithm. It processes digits by grouping numbers by each digit, from least significant to most significant.
Radix sort has O(nk) time complexity, where n is the number of elements and k is the number of digits in the longest number. It's efficient for large datasets.
Numeric Radix Sort (Ascending)
This example demonstrates radix sort for positive integers in ascending order.
<?php
function radixSort(array $arr): array {
$maxDigits = max(array_map('strlen', array_map('strval', $arr)));
for ($digit = 0; $digit < $maxDigits; $digit++) {
$buckets = array_fill(0, 10, []);
foreach ($arr as $num) {
$digitVal = (int) (($num / (10 ** $digit)) % 10);
$buckets[$digitVal][] = $num;
}
$arr = array_merge(...$buckets);
}
return $arr;
}
$numbers = [170, 45, 75, 90, 802, 24, 2, 66];
$sorted = radixSort($numbers);
print_r($sorted); // [2, 24, 45, 66, 75, 90, 170, 802]
The algorithm processes each digit position, distributing numbers into buckets based on the current digit, then collects them in order.
Numeric Radix Sort (Descending)
This modified version sorts numbers in descending order by reversing bucket order.
<?php
function radixSortDesc(array $arr): array {
$maxDigits = max(array_map('strlen', array_map('strval', $arr)));
for ($digit = 0; $digit < $maxDigits; $digit++) {
$buckets = array_fill(0, 10, []);
foreach ($arr as $num) {
$digitVal = (int) (($num / (10 ** $digit)) % 10);
$buckets[$digitVal][] = $num;
}
$arr = array_merge(...array_reverse($buckets));
}
return $arr;
}
$numbers = [170, 45, 75, 90, 802, 24, 2, 66];
$sorted = radixSortDesc($numbers);
print_r($sorted); // [802, 170, 90, 75, 66, 45, 24, 2]
The only change from ascending sort is reversing the buckets before merging. This gives us the descending order result.
String Radix Sort (Ascending)
Radix sort can also sort strings alphabetically by processing characters.
<?php
function stringRadixSort(array $arr): array {
$maxLength = max(array_map('strlen', $arr));
for ($pos = $maxLength - 1; $pos >= 0; $pos--) {
$buckets = array_fill(0, 256, []);
foreach ($arr as $str) {
$char = $pos < strlen($str) ? ord($str[$pos]) : 0;
$buckets[$char][] = $str;
}
$arr = array_merge(...$buckets);
}
return $arr;
}
$words = ["apple", "banana", "kiwi", "orange", "pear"];
$sorted = stringRadixSort($words);
print_r($sorted); // ["apple", "banana", "kiwi", "orange", "pear"]
This processes strings from right to left, using ASCII values for character comparison. Shorter strings are treated as having null characters.
String Radix Sort (Descending)
For descending alphabetical order, we reverse the bucket merging order.
<?php
function stringRadixSortDesc(array $arr): array {
$maxLength = max(array_map('strlen', $arr));
for ($pos = $maxLength - 1; $pos >= 0; $pos--) {
$buckets = array_fill(0, 256, []);
foreach ($arr as $str) {
$char = $pos < strlen($str) ? ord($str[$pos]) : 0;
$buckets[$char][] = $str;
}
$arr = array_merge(...array_reverse($buckets));
}
return $arr;
}
$words = ["apple", "banana", "kiwi", "orange", "pear"];
$sorted = stringRadixSortDesc($words);
print_r($sorted); // ["pear", "orange", "kiwi", "banana", "apple"]
The descending version reverses the buckets before merging, similar to the numeric descending sort implementation.
Radix Sort vs Quick Sort Benchmark
Let's compare radix sort with quick sort performance on large datasets.
<?php
function generateRandomNumbers(int $count): array {
$numbers = [];
for ($i = 0; $i < $count; $i++) {
$numbers[] = rand(1000, 999999);
}
return $numbers;
}
function benchmark(callable $sortFunc, array $data): float {
$start = microtime(true);
$sortFunc($data);
return microtime(true) - $start;
}
$largeDataset = generateRandomNumbers(100000);
$radixTime = benchmark('radixSort', $largeDataset);
$quickTime = benchmark(function($arr) { sort($arr); }, $largeDataset);
echo "Radix sort time: " . number_format($radixTime, 4) . " seconds\n";
echo "Quick sort time: " . number_format($quickTime, 4) . " seconds\n";
On a typical test with 100,000 numbers, radix sort often outperforms quick sort for integer data, especially when numbers have limited digit lengths.
When to Use Radix Sort
- Fixed-width keys: Ideal for sorting numbers or fixed-length strings
- Large datasets: Efficient O(n) performance for suitable data
- Stable sort needed: Maintains relative order of equal elements
- Integer sorting: Particularly effective for integer data types
Limitations of Radix Sort
- Data constraints: Works best with fixed-size keys
- Memory usage: Requires additional space for buckets
- Negative numbers: Needs special handling for signed integers
- Floating points: Not directly suitable for floating-point numbers
Source
This tutorial covered the radix sort algorithm in PHP with examples for both numeric and textual data in ascending and descending order.