Perl sort blocks and the Schwartzian transform
Sort numbers, hash keys by value, and records by computed keys without recomputing the keys.
On this page
Perl arrays, hashes, and map.
- Sort numbers, hash keys by value, and records by computed keys without recomputing the keys.
- Predict the sample output and explain the state changes.
- Complete the practice task and check the boundary cases.
The concept
Perl's sort without a block sorts as strings, so 10 comes before 9. A sort block receives the two elements to compare in the special variables $a and $b and returns a negative number, zero, or a positive number. <=> compares numbers and cmp compares strings. The keyword or chains comparisons, so a second key is used only when the first is equal. reverse flips a sorted list.
The Schwartzian transform avoids recomputing an expensive key during the sort. First map each element to a pair of its key and itself, then sort the pairs by the key, and finally map back to the elements. Here the key is the word length, but it could be anything costly. Perl's sort is stable in practice and runs in O(n log n).
Code example
use strict;
use warnings;
my @nums = (10, 9, 1, 25);
print join(" ", sort @nums), "\n";
print join(" ", sort { $a <=> $b } @nums), "\n";
print join(" ", reverse sort { $a <=> $b } @nums), "\n";
my %age = (Ada => 30, Bo => 25, Cy => 30, Di => 25);
my @by_age = sort { $age{$b} <=> $age{$a} or $a cmp $b } keys %age;
print "@by_age\n";
my @words = qw(pear fig apple kiwi);
my @by_length =
map { $_->[1] }
sort { $a->[0] <=> $b->[0] or $a->[1] cmp $b->[1] }
map { [length($_), $_] } @words;
print "@by_length\n";1 10 25 9 1 9 10 25 25 10 9 1 Ada Cy Bo Di fig kiwi pear apple
Follow the code
Open the walkthrough to inspect the example one step at a time.
Show guided walkthrough
use strict;use warnings; my @nums = (10, 9, 1, 25);print join(" ", sort @nums), "\n";print join(" ", sort { $a <=> $b } @nums), "\n";print join(" ", reverse sort { $a <=> $b } @nums), "\n"; my %age = (Ada => 30, Bo => 25, Cy => 30, Di => 25);my @by_age = sort { $age{$b} <=> $age{$a} or $a cmp $b } keys %age;print "@by_age\n"; my @words = qw(pear fig apple kiwi);my @by_length = map { $_->[1] } sort { $a->[0] <=> $b->[0] or $a->[1] cmp $b->[1] } map { [length($_), $_] } @words;print "@by_length\n";Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Without a block, sort compares as strings, so 10 sorts before 9. | — | 1 10 25 9 | |
| The block uses <=> for numeric order. | — | 1 10 25 9 1 9 10 25 | |
| reverse turns ascending into descending. | — | 1 10 25 9 1 9 10 25 25 10 9 1 | |
| Sort the keys by their values, highest first, and by name when the values tie. | — | 1 10 25 9 1 9 10 25 25 10 9 1 | |
| Ada and Cy (30), then Bo and Di (25). | — | 1 10 25 9 1 9 10 25 25 10 9 1 Ada Cy Bo Di | |
| Step 1: pair each word with its length. Step 2 sorts the pairs and step 3, at the top, extracts the words. | — | 1 10 25 9 1 9 10 25 25 10 9 1 Ada Cy Bo Di | |
| Sorted by length, then alphabetically. | — | 1 10 25 9 1 9 10 25 25 10 9 1 Ada Cy Bo Di fig kiwi pear apple |
Behind the scenes
How Perl processes this code
Perl compiles the script internally before executing it. strict and warnings help identify mistakes.
Cost and common mistakes
O(n log n) comparisons; the transform adds O(n) to compute the keys once.
- Never use $a and $b as ordinary variable names, because sort uses them. Declaring my $a breaks sort blocks.
- Hash key order is random in Perl, so always sort keys before printing them.
- The Schwartzian transform only pays off when computing the key is expensive. For cheap keys a plain sort block is fine.
Try it yourself
How would you sort the words in reverse alphabetical order?
Reveal answer and reasoning
sort { $b cmp $a } @words, or reverse sort @words.