Daftar Isi

• NAME
• SYNOPSIS
• DESCRIPTION
• CAVEATS

NAME

sort - perl pragma to control sort() behaviour

SYNOPSIS

 use sort 'stable';# guarantee stability
 
 use sort '_quicksort';# use a quicksort algorithm
 
 use sort '_mergesort';# use a mergesort algorithm
 
 use sort 'defaults';# revert to default behavior
 
 no  sort 'stable';# stability not important
 
 
 use sort '_qsort';# alias for quicksort
 
 
 my $current;
 
 BEGIN {
 
$current = sort::current();# identify prevailing algorithm
 
 }
 

DESCRIPTION

With the sort pragma you can control the behaviour of the builtinsort() function.

In Perl versions 5.6 and earlier the quicksort algorithm was used toimplement sort(), but in Perl 5.8 a mergesort algorithm was also madeavailable, mainly to guarantee worst case O(N log N) behaviour:the worst case of quicksort is O(N**2). In Perl 5.8 and later,quicksort defends against quadratic behaviour by shuffling largearrays before sorting.

A stable sort means that for records that compare equal, the originalinput ordering is preserved. Mergesort is stable, quicksort is not.Stability will matter only if elements that compare equal can bedistinguished in some other way. That means that simple numericaland lexical sorts do not profit from stability, since equal elementsare indistinguishable. However, with a comparison such as

   { substr($a, 0, 3) cmp substr($b, 0, 3) }
 

stability might matter because elements that compare equal on thefirst 3 characters may be distinguished based on subsequent characters.In Perl 5.8 and later, quicksort can be stabilized, but doing so willadd overhead, so it should only be done if it matters.

The best algorithm depends on many things. On average, mergesortdoes fewer comparisons than quicksort, so it may be better whencomplicated comparison routines are used. Mergesort also takesadvantage of pre-existing order, so it would be favored for usingsort() to merge several sorted arrays. On the other hand, quicksortis often faster for small arrays, and on arrays of a few distinctvalues, repeated many times. You can force thechoice of algorithm with this pragma, but this feels heavy-handed,so the subpragmas beginning with a _ may not persist beyond Perl 5.8.The default algorithm is mergesort, which will be stable even ifyou do not explicitly demand it.But the stability of the default sort is a side-effect that couldchange in later versions. If stability is important, be sure tosay so with a

  use sort 'stable';
 

The no sort pragma doesn'tforbid what follows, it just leaves the choice open. Thus, after

  no sort qw(_mergesort stable);
 

a mergesort, which happens to be stable, will be employed anyway.Note that

  no sort "_quicksort";
 
  no sort "_mergesort";
 

have exactly the same effect, leaving the choice of sort algorithm open.

CAVEATS

As of Perl 5.10, this pragma is lexically scoped and takes effectat compile time. In earlier versions its effect was global and tookeffect at run-time; the documentation suggested using eval() tochange the behaviour:

  { eval 'use sort qw(defaults _quicksort)'; # force quicksort
 
 eval 'no sort "stable"';  # stability not wanted
 
 print sort::current . "\n";
 
 @a = sort @b;
 
 eval 'use sort "defaults"';   # clean up, for others
 
  }
 
  { eval 'use sort qw(defaults stable)'; # force stability
 
 print sort::current . "\n";
 
 @c = sort @d;
 
 eval 'use sort "defaults"';   # clean up, for others
 
  }
 

Such code no longer has the desired effect, for two reasons.Firstly, the use of eval() means that the sorting algorithmis not changed until runtime, by which time it's too late tohave any effect. Secondly, sort::current is also called atrun-time, when in fact the compile-time value of sort::currentis the one that matters.

So now this code would be written:

  { use sort qw(defaults _quicksort); # force quicksort
 
 no sort "stable";  # stability not wanted
 
 my $current;
 
 BEGIN { $current = print sort::current; }
 
 print "$current\n";
 
 @a = sort @b;
 
 # Pragmas go out of scope at the end of the block
 
  }
 
  { use sort qw(defaults stable); # force stability
 
 my $current;
 
 BEGIN { $current = print sort::current; }
 
 print "$current\n";
 
 @c = sort @d;
 
  }