=over

=item sort SUBNAME LIST
X<sort> X<qsort> X<quicksort> X<mergesort>

=item sort BLOCK LIST

=item sort LIST

In list context, this sorts the LIST and returns the sorted list value.
In scalar context, the behaviour of C<sort()> is undefined.

If SUBNAME or BLOCK is omitted, C<sort>s in standard string comparison
order.  If SUBNAME is specified, it gives the name of a subroutine
that returns an integer less than, equal to, or greater than C<0>,
depending on how the elements of the list are to be ordered.  (The 
C<< <=> >> and C<cmp> operators are extremely useful in such routines.)
SUBNAME may be a scalar variable name (unsubscripted), in which case
the value provides the name of (or a reference to) the actual
subroutine to use.  In place of a SUBNAME, you can provide a BLOCK as
an anonymous, in-line sort subroutine.

If the subroutine's prototype is C<($$)>, the elements to be compared are
passed by reference in C<@_>, as for a normal subroutine.  This is slower
than unprototyped subroutines, where the elements to be compared are passed
into the subroutine as the package global variables $a and $b (see example
below).  Note that in the latter case, it is usually highly counter-productive
to declare $a and $b as lexicals.

If the subroutine is an XSUB, the elements to be compared are pushed on to
the stack, the way arguments are usually passed to XSUBs.  $a and $b are
not set.

The values to be compared are always passed by reference and should not
be modified.

You also cannot exit out of the sort block or subroutine using any of the
loop control operators described in L<perlsyn> or with C<goto>.

When C<use locale> (but not C<use locale 'not_characters'>) is in
effect, C<sort LIST> sorts LIST according to the
current collation locale.  See L<perllocale>.

sort() returns aliases into the original list, much as a for loop's index
variable aliases the list elements.  That is, modifying an element of a
list returned by sort() (for example, in a C<foreach>, C<map> or C<grep>)
actually modifies the element in the original list.  This is usually
something to be avoided when writing clear code.

Perl 5.6 and earlier used a quicksort algorithm to implement sort.
That algorithm was not stable, so I<could> go quadratic.  (A I<stable> sort
preserves the input order of elements that compare equal.  Although
quicksort's run time is O(NlogN) when averaged over all arrays of
length N, the time can be O(N**2), I<quadratic> behavior, for some
inputs.)  In 5.7, the quicksort implementation was replaced with
a stable mergesort algorithm whose worst-case behavior is O(NlogN).
But benchmarks indicated that for some inputs, on some platforms,
the original quicksort was faster.  5.8 has a sort pragma for
limited control of the sort.  Its rather blunt control of the
underlying algorithm may not persist into future Perls, but the
ability to characterize the input or output in implementation
independent ways quite probably will.  See L<the sort pragma|sort>.

Examples:

    # sort lexically
    @articles = sort @files;

    # same thing, but with explicit sort routine
    @articles = sort {$a cmp $b} @files;

    # now case-insensitively
    @articles = sort {fc($a) cmp fc($b)} @files;

    # same thing in reversed order
    @articles = sort {$b cmp $a} @files;

    # sort numerically ascending
    @articles = sort {$a <=> $b} @files;

    # sort numerically descending
    @articles = sort {$b <=> $a} @files;

    # this sorts the %age hash by value instead of key
    # using an in-line function
    @eldest = sort { $age{$b} <=> $age{$a} } keys %age;

    # sort using explicit subroutine name
    sub byage {
        $age{$a} <=> $age{$b};  # presuming numeric
    }
    @sortedclass = sort byage @class;

    sub backwards { $b cmp $a }
    @harry  = qw(dog cat x Cain Abel);
    @george = qw(gone chased yz Punished Axed);
    print sort @harry;
        # prints AbelCaincatdogx
    print sort backwards @harry;
        # prints xdogcatCainAbel
    print sort @george, 'to', @harry;
        # prints AbelAxedCainPunishedcatchaseddoggonetoxyz

    # inefficiently sort by descending numeric compare using
    # the first integer after the first = sign, or the
    # whole record case-insensitively otherwise

    my @new = sort {
        ($b =~ /=(\d+)/)[0] <=> ($a =~ /=(\d+)/)[0]
                            ||
                    fc($a)  cmp  fc($b)
    } @old;

    # same thing, but much more efficiently;
    # we'll build auxiliary indices instead
    # for speed
    my @nums = @caps = ();
    for (@old) {
        push @nums, ( /=(\d+)/ ? $1 : undef );
        push @caps, fc($_);
    }

    my @new = @old[ sort {
                           $nums[$b] <=> $nums[$a]
                                    ||
                           $caps[$a] cmp $caps[$b]
                         } 0..$#old
                  ];

    # same thing, but without any temps
    @new = map { $_->[0] }
           sort { $b->[1] <=> $a->[1]
                           ||
                  $a->[2] cmp $b->[2]
           } map { [$_, /=(\d+)/, fc($_)] } @old;

    # using a prototype allows you to use any comparison subroutine
    # as a sort subroutine (including other package's subroutines)
    package other;
    sub backwards ($$) { $_[1] cmp $_[0]; }  # $a and $b are
                                             # not set here    
    package main;
    @new = sort other::backwards @old;

    # guarantee stability, regardless of algorithm
    use sort 'stable';
    @new = sort { substr($a, 3, 5) cmp substr($b, 3, 5) } @old;

    # force use of mergesort (not portable outside Perl 5.8)
    use sort '_mergesort';  # note discouraging _
    @new = sort { substr($a, 3, 5) cmp substr($b, 3, 5) } @old;

Warning: syntactical care is required when sorting the list returned from
a function.  If you want to sort the list returned by the function call
C<find_records(@key)>, you can use:

    @contact = sort { $a cmp $b } find_records @key;
    @contact = sort +find_records(@key);
    @contact = sort &find_records(@key);
    @contact = sort(find_records(@key));

If instead you want to sort the array @key with the comparison routine
C<find_records()> then you can use:

    @contact = sort { find_records() } @key;
    @contact = sort find_records(@key);
    @contact = sort(find_records @key);
    @contact = sort(find_records (@key));

If you're using strict, you I<must not> declare $a
and $b as lexicals.  They are package globals.  That means
that if you're in the C<main> package and type

    @articles = sort {$b <=> $a} @files;

then C<$a> and C<$b> are C<$main::a> and C<$main::b> (or C<$::a> and C<$::b>),
but if you're in the C<FooPack> package, it's the same as typing

    @articles = sort {$FooPack::b <=> $FooPack::a} @files;

The comparison function is required to behave.  If it returns
inconsistent results (sometimes saying C<$x[1]> is less than C<$x[2]> and
sometimes saying the opposite, for example) the results are not
well-defined.

Because C<< <=> >> returns C<undef> when either operand is C<NaN>
(not-a-number), be careful when sorting with a
comparison function like C<< $a <=> $b >> any lists that might contain a
C<NaN>.  The following example takes advantage that C<NaN != NaN> to
eliminate any C<NaN>s from the input list.

    @result = sort { $a <=> $b } grep { $_ == $_ } @input;

=back