It surely has to be faster to do a short-circuiting, worst-case O(N) pass to determine if the sort is necessary before performing an O(N log N ) sort, than to perform the uneeded sort and then perform an O(2+a bit N) pass to see if it was necessary.

The advantage will vary with how often the array needs sorting, but with a simple 50:50 split, and the pre-check done in perl, it seems to be at least 1/3 faster:

#! perl -slw
use strict;
use List::Util qw[ shuffle ];
use Benchmark qw[ cmpthese ];
use Digest::MD5 qw[ md5 ];

open my $fh, '<', 'words' or die $!;
my @sorted =  <$fh>;
close $fh;
my @shuffled = shuffle @sorted;

cmpthese( 10, {
     join   => sub{
         my @resorted1 = sort @sorted;
         my $r1 = join( '|', @resorted1 ) eq join( '|', @sorted );
         my @resorted2 = sort @shuffled;
         my $r2 = join( '|', @resorted2 ) eq join( '|', @shuffled );
     },
     md5    => sub{
         my @resorted1 = sort @sorted;
         my $r1 = md5( @resorted1 ) eq md5( @sorted );
         my @resorted2 = sort @shuffled;
         my $r2 = md5( @resorted2 ) eq md5( @shuffled );
     },
     CheckFirst => sub{
         my $sortNeeded = 0;
         for( 1 .. $#sorted ){ 
             $sorted[ $_ -1 ] gt  $sorted[ $_ ] 
                 and $sortNeeded = 1 and last 
         }
         my @resorted1 = sort @sorted if $sortNeeded;
         $sortNeeded = 0;
         for( 1 .. $#shuffled ){ 
             $shuffled[ $_ -1 ] gt $shuffled[ $_ ] 
                 and $sortNeeded = 1 and last 
         }
         my @resorted2 = sort @shuffled if $sortNeeded;
     },
});

__END__
C:\test>junk7
             Rate       join        md5 CheckFirst
join       1.03/s         --        -1%       -25%
md5        1.04/s         1%         --       -25%
CheckFirst 1.38/s        33%        32%         --

C:\test>junk7
             Rate       join        md5 CheckFirst
join       1.03/s         --        -0%       -25%
md5        1.04/s         0%         --       -25%
CheckFirst 1.38/s        34%        33%         --

C:\test>junk7
             Rate       join        md5 CheckFirst
join       1.03/s         --        -2%       -25%
md5        1.05/s         2%         --       -24%
CheckFirst 1.37/s        34%        31%         --
[download]