Schwartzian Transform - Efficiency Analysis

Efficiency Analysis

Without the Schwartzian transform, the sorting in the example above would be written in Perl like this:

@sorted = sort { foo($a) cmp foo($b) } @unsorted;

While it is shorter to code, the naive approach here could be much less efficient if the key function (called foo in the example above) is expensive to compute. This is because the code inside the brackets is evaluated each time two elements needs to be compared. An optimal comparison sort performs O(n log n) comparisons (where n is the length of the list), with 2 calls to foo every comparison, resulting in O(n log n) calls to foo. In comparison, using the Schwartzian transform, we only make 1 call to foo per element, at the beginning map stage, for a total of n calls to foo.

However, if the function foo is relatively simple, then the extra overhead of the Schwartzian transform may be unwarranted.