Schwartzian Transform (was Re: Sort)

[Tim Peters]

[posted & mailed]

[Alex Martelli]
> The technique is named after its inventor Randall
> Schwartz, who thought it up in the context of Perl
> (but it works even better in Python:-).  The key
> idea is that, in scripting languages such as Perl
> and Python, 'sort' slows down a lot if each of its
> O(N log N) comparison involves interpreting script
> code, rather than just the fast, built-in "lexical
> comparison" that the language provides.

[Jay O'Connor]
> Why is it better in Python than Perl?
>
> This subject came up recently about Perl and list handling in
> another context, so I'm curious

Python's builtin sequence comparison is lexicographic (the sequence elements
are compared one at a time, left to right, until the first pair that "breaks
a tie" is found).  In Perl you need to fake that by hand, usually via
chaining together spaceship (<=> or cmp) operators.

besides-which-*everything's*-better-in-python<wink>-ly y'rs  - tim