A Simple Pattern That Makes Sorting in PHP Faster

Sorting arrays in PHP using a custom sorting criterion is simple thanks to the usort() function. But if you are not careful, it can be much slower than you expect.

Consider this example: you have a list of CSS rules represented as PHP classes and you need to sort them by specificity. Each rule exposes a getSpecificity() method that does some regex work internally. A natural first implementation looks like this:

usort($rules, function (Rule $a, Rule $b): int {
    return $a->getSpecificity() <=> $b->getSpecificity();
});

This code is correct, clean, readable ... and slow.

The hidden performance issue: a comparison sort typically performs n log(n) comparisons. Each comparison requires calling your callback, which in turn computes the sort key for both elements.

In this example, getSpecificity() is recomputed over and over again for the same objects during the sort. For a list of 100 rules, this means hundreds of comparisons and thousands of calls to getSpecificity().

In cases like this when the sort key is expensive to compute, there's a better way to do it.

The three step pattern

The optimization is to compute the expensive key once per element following a three-step pattern: decorate, sort, undecorate:

// Step 1: decorate (compute the expensive key once) and return [$rule, key] pairs
$decorated = array_map(
    static fn (Rule $rule): array => [$rule, $rule->getSpecificity()],
    $rules
);

// Step 2: sort using the cached key
usort($decorated, static fn (array $a, array $b): int => $a[1] <=> $b[1]);

// Step 3: undecorate (extract the original values)
$rules = array_column($decorated, 0);

Now getSpecificity() is called exactly once per rule, during the array_map() pass. The usort() comparisons only deal with integers and the total number of calls to the expensive method goes from O(n log n) to O(n).

This pattern is called the Schwartzian transform, named after Randal L. Schwartz, who popularized it in Perl back in 1994. The core idea comes from a Lisp idiom known as "decorate-sort-undecorate" (DSU).

This concept is language-agnostic: Python's sorted() has a built-in key= parameter that does the same thing, Ruby has sort_by, Haskell has sortOn. PHP does not have a native equivalent, but there's a trick you can use.

The array_multisort() trick

The array_multisort() PHP function can sort several arrays at once, or a multi-dimensional array by one or more dimensions. It's not very popular (60k usages on GitHub) compared to other array functions (e.g. 640k array_values() usages, 400k array_pop() usages, etc.), but it's very useful for Schwartzian transforms.

This is how it works. Consider this initial array:

$items = [
    ['category' => 2, 'priority' => 10, 'name' => 'Deploy'],
    ['category' => 1, 'priority' => 20, 'name' => 'Write docs'],
    ['category' => 2, 'priority' => 30, 'name' => 'Run tests'],
    ['category' => 1, 'priority' => 10, 'name' => 'Fix bug'],
];

If you need to sort it by both category (first) and priority (second), you can do this:

// extract the sorting keys first
$categories = array_column($items, 'category');
$priorities = array_column($items, 'priority');

// PHP sorts items ASC by category first and then, inside each
// category group, it sorts items DESC by priority
array_multisort($categories, SORT_ASC, $priorities, SORT_DESC, $items);

After sorting, the $items array is:

[
    ['category' => 1, 'priority' => 20, 'name' => 'Write docs'],
    ['category' => 1, 'priority' => 10, 'name' => 'Fix bug'],
    ['category' => 2, 'priority' => 30, 'name' => 'Run tests'],
    ['category' => 2, 'priority' => 10, 'name' => 'Deploy'],
]

Using array_multisort(), the "decorate, sort, undecorate" pattern becomes as simple as:

$keys = array_map(static fn (Rule $rule): int => $rule->getSpecificity(), $rules);
array_multisort($keys, SORT_ASC, $rules);

A real-world case in Symfony

tijsverkoyen/CssToInlineStyles is a popular PHP library (and an optional Symfony dependency) that converts CSS stylesheets to inline styles. Internally, it sorts CSS rules by specificity before applying them to DOM nodes.

In a real profiling session when running tests on a Symfony app, sortOnSpecificity() appeared in the flame graph with 104,000 calls triggering 126,000 calls to an inner compareTo() method. The sort was costing almost 200 ms out of a total runtime of 4 seconds, which looked excessive.

The original sortOnSpecificity() method used a usort() callback that called getValue() and getOrder() on every comparison:

// original code (simplified)
usort($rules, function (Rule $a, Rule $b): int {
    $aSpecificity = $a->getSpecificity();
    $bSpecificity = $b->getSpecificity();

    if ($aSpecificity->getValue() === $bSpecificity->getValue()) {
        return $a->getOrder() <=> $b->getOrder();
    }

    return $aSpecificity->getValue() <=> $bSpecificity->getValue();
});

The optimization was a direct application of the Schwartzian transform: compute the sortable keys once and let array_multisort() handle the ordering:

$specificityValues = [];
$orders = [];

foreach ($rules as $rule) {
    $specificityValues[] = $rule->getSpecificity()->getValue();
    $orders[] = $rule->getOrder();
}

array_multisort($specificityValues, SORT_ASC, $orders, SORT_ASC, $rules);

After this change, sortOnSpecificity() disappeared from the hot path in the profiler and the wall time improved by roughly 200 milliseconds.

You can see the full change in this pull request: PR #260

When to apply this technique

The Schwartzian transform is recommended only when:

• The sort key is expensive to compute (I/O, regex, database queries, complex calculations)
• You do not need memoization across multiple sorts. You just want each element's key computed once per sort invocation

If your sort key is a simple property access like $a->name, the overhead of decorating and undecorating is probably not worth it. The transform shines when the key computation has real cost.

---

✨ If you liked this post, consider sponsoring me on GitHub 🙌