There’s not a whole lot of PHP algorithms floating around. Perhaps people just rely upon the SPL. I had a curiosity to find a string sorting algorithm written in PHP and I didn’t find any non array-based solutions. The implementation I came up with this morning implements recursion, passing by reference, and string iteration. It’s worth noting that this is a horribly slow solution. For this reason I’ve included a very concise solution which is an order of magnitude faster as it uses a C implementation of quicksort which generally runs in O(nlogn). To make people aware of quicksort, I have also implemented a solution for string sorting. With that being said, this could be a fun exercise for students. Alternative solutions and runtime analysis are welcome in the comments section.

Version 1 (slow)

Let’s be honest, if I didn’t use a pre-existing algorithm to create a function, odds are it’s going to be slow. This implementation most closely resembles a version of Bubble Sort without comparing apples to apples.

/**
 * A (slow) non-array based solution for sorting strings in PHP.
 *
 * @param	&$s	The string to be sorted
 * @param	$len	The length of the string
 * @param	$curPos	The current position being sorted (default = 0)
 */
function sortString(&$s, $len = 0, $curPos = 0) {
        if ($curPos === $len) return;
        $nextPos = $curPos + 1;
        while ($nextPos < $len) {
                if ($s{$nextPos} < $s{$curPos}) {
                        $tmp = $s{$curPos};
                        $s{$curPos} = $s{$nextPos};
                        $s{$nextPos} = $tmp;
                }
                ++$nextPos;
        }
        sortString($s, $len, $curPos + 1);
}

// example usage prints:
// 1223344789aaaaadddefffffhhhiillllnnoorrsssuuuuwyy
$string = 'ouhlasfuywernhlasdfoulnarfiuyadf1234987234sdfailh';
sortString($string, strlen($string));
echo $string . "\n";

Version 2 – Quicksort Implementation

Although much faster than version 1, even a user defined quicksort implementation in PHP cannot compare to that of sort.

function sortString($s) {
        $left = $right = '';
        $l = strlen($s) - 1;
        if ($l <= 0) return $s;
        $pivot = floor($l/2);
        do {
                if ($l == $pivot) continue;
                if ($s[$l] <= $s[$pivot]) $left .= $s[$l];
                else $right .= $s[$l];
        } while (--$l);
        return sortString($left) . $s[$pivot] . sortString($right);
}

// example usage prints:
// 1223344789aaaaadddefffffhhhiillllnnoorrsssuuuuwyy
$string = 'ouhlasfuywernhlasdfoulnarfiuyadf1234987234sdfailh';
$string = sortString($string);
echo $string . "\n";

Version 3 – Fast and Concise

This version, although utilizing some fairly heavy functions like split and implode, still outperforms both previous solutions. This is due to the fact it utilizes a small subset of PHP core functions. The core PHP functions have heavily optimized implementations which are written directly in C, meaning it’s nearly impossible to get much faster except in small edge cases.

function sortString(&$s) {
	$s = str_split($s);
	sort($s);
	$s = implode($s);
}

// example usage prints:
// 1223344789aaaaadddefffffhhhiillllnnoorrsssuuuuwyy
$string = 'ouhlasfuywernhlasdfoulnarfiuyadf1234987234sdfailh';
sortString($string, strlen($string));
echo $string . "\n";