---
name: sorting performance
---
# Sorting

[`sort`](../../p5/core/perlfunc/sort) is where a surprising amount of
a program's time hides, because the cost is not the sort - it is the
comparator, called O(n log n) times. A comparator that does real work
per call multiplies that work by the log of the list size. This
chapter is about recognising when the comparator is the bottleneck
and the two transforms that fix it.

The reference page for [`sort`](../../p5/core/perlfunc/sort) defines
the operator, the comparator contract, and the `$a`/`$b` mechanics.
This chapter assumes you know those and focuses on speed.

## The comparator is the cost

`sort` itself is a stable mergesort - fast, and not something you can
improve from Perl. What you control is how much work happens *inside*
each comparison. Two facts set the budget:

- The comparator runs O(n log n) times. For a 100,000-element list
  that is well over a million calls.
- On pperl, the comparator block is a callback, and callbacks run on
  the interpreter. The JIT compiles loops, not `sort` comparator
  bodies (see [JIT compilation](../pperl-architecture/jit)), so you
  cannot rely on the JIT to rescue an expensive comparator the way it
  rescues a numeric loop. The comparator's cost is paid in full,
  every call.

That second fact is the pperl-specific reason the transforms below
matter as much here as on upstream Perl - arguably more, because the
JIT's speedups elsewhere make an un-transformed sort stand out more
sharply in a profile.

The diagnosis is always the same: if [Measuring](measuring) shows
time concentrated in a comparator, the key is being recomputed on
every comparison. Compute it once instead.

## The Schwartzian transform

When the sort key is expensive to derive from each element - a
substring extraction, a field lookup, a length, a computation - the
naive sort recomputes it on every comparison:

```perl
# Slow: the key (-M $_) is computed twice per comparison, O(n log n) times.
my @sorted = sort { -M $a <=> -M $b } @files;
```

The Schwartzian transform computes each key exactly once, sorts on
the precomputed key, then discards it - a `map`, a `sort`, a `map`:

```perl
my @sorted =
    map  { $_->[1] }                      # 3. strip the key, keep the element
    sort { $a->[0] <=> $b->[0] }          # 2. sort on the precomputed key
    map  { [ -M $_, $_ ] }                # 1. compute the key once per element
    @files;
```

Read it bottom to top: the lower `map` builds a `[key, element]` pair
for each element (n key computations), the `sort` compares only the
cheap precomputed `$_->[0]` (no key computation in the comparator),
and the upper `map` throws the key away. The expensive key is computed
n times instead of O(n log n) times.

Use it whenever the key costs more than a numeric or string compare to
derive. For a 100,000-element list sorted by a key that takes a
microsecond to compute, the naive form spends seconds in key
computation alone; the transform spends a tenth of a second.

The pieces are [`map`](../../p5/core/perlfunc/map) and
[`sort`](../../p5/core/perlfunc/sort) - the
[`sort`](../../p5/core/perlfunc/sort) reference page shows the same
transform as a worked example.

## The Guttman-Rosler transform

The Schwartzian transform sorts arrayrefs, which costs an arrayref
allocation and a dereference per comparison. When the key can be
encoded as a fixed-width *string* prefix, the Guttman-Rosler transform
(GRT) goes further: it packs the key and the element into a single
string, sorts those strings with the default string `sort` (no
comparator block at all), then strips the prefix.

```perl
my @sorted =
    map  { substr($_, 8) }                          # 3. strip the 8-char key prefix
    sort                                            # 2. plain string sort, no comparator
    map  { pack('N', $_->{priority}) . $_->{name} } # 1. fixed-width key + payload
    @records;
```

The win has two parts. First, the key is precomputed once, as in the
Schwartzian. Second - and this is the GRT's distinct advantage - the
`sort` has *no comparator block*, so there is no per-comparison
callback at all. Default string `sort` compares the packed strings
directly, which avoids the callback cost entirely. Removing the
comparator callback matters more on pperl precisely because that
callback would run on the interpreter.

The cost of the GRT is that the key must be encodable so that a
bytewise string comparison produces the order you want:

- Integers must be packed big-endian (`pack 'N'` / `pack 'Q>'`) so
  that byte order matches numeric order, and offset to be non-negative
  (string comparison has no sign bit).
- Floats and signed numbers need bias encoding to sort correctly as
  bytes - fiddly enough that the Schwartzian is usually the better
  choice unless the sort is genuinely hot.
- Every key must be the *same width*, or a short key's payload bleeds
  into the comparison.

Reach for the GRT when the sort is hot, the key is an unsigned integer
or a string, and the Schwartzian still shows up in the profile. For
anything else, the Schwartzian is simpler and almost always fast
enough.

## Cheaper comparators without a transform

Not every slow sort needs a transform. Sometimes the comparator is
just written more expensively than it needs to be.

- **Compare numbers with `<=>`, strings with `cmp`.** Using `cmp` on
  numbers stringifies both sides every comparison; using `<=>` on
  strings is a numification trap. Match the operator to the data.
- **Order tiebreakers cheapest-first.** A multi-key comparator with
  `||` stops at the first non-zero result. Put the discriminating,
  cheap key first so most comparisons never reach the expensive one:

  ```perl
  sort { $a->{rank} <=> $b->{rank}        # cheap, decides most pairs
      || $a->{name} cmp $b->{name} }      # only when ranks tie
         @rows;
  ```

- **Sort once, reverse separately.** To sort descending, sorting
  ascending and calling [`reverse`](../../p5/core/perlfunc/reverse) is
  often clearer and no slower than inverting the comparator, and it
  keeps the comparator in its cheapest form.

## Decision order

1. Profile. If [Measuring](measuring) does not put the time in the
   sort, leave it alone.
2. If the comparator recomputes a key, apply the Schwartzian
   transform. This fixes the great majority of slow sorts.
3. If the sort is still hot and the key is an unsigned integer or a
   string, consider the Guttman-Rosler transform to drop the
   comparator callback entirely.
4. Re-measure after each change.

## See also

- [`sort`](../../p5/core/perlfunc/sort) - the operator reference:
  comparator contract, `$a`/`$b`, stability.
- [`map`](../../p5/core/perlfunc/map) - the transform half of both
  the Schwartzian and Guttman-Rosler forms.
- [`reverse`](../../p5/core/perlfunc/reverse) - descending sorts
  without inverting the comparator.
- [Measuring](measuring) - confirm the comparator is the cost before
  transforming it.
- [JIT compilation](../pperl-architecture/jit) - why a `sort`
  comparator block is not JIT-compiled, so its cost is paid in full.