lib/sort.pm

   1 package sort;
   2
   3 our $VERSION = '1.00';
   4
   5 $sort::hint_bits       = 0x00020000; # HINT_LOCALIZE_HH, really...
   6
   7 $sort::quicksort_bit   = 0x00000001;
   8 $sort::mergesort_bit   = 0x00000002;
   9 $sort::sort_bits       = 0x000000FF; # allow 256 different ones
  10 $sort::stable_bit      = 0x00000100;
  11
  12 use strict;
  13
  14 sub import {
  15     shift;
  16     if (@_ == 0) {
  17         require Carp;
  18         Carp::croak("sort pragma requires arguments");
  19     }
  20     $^H |= $sort::hint_bits;
  21     local $_;
  22     no warnings 'uninitialized';        # $^H{SORT} bitops would warn
  23     while ($_ = shift(@_)) {
  24         if (/^_q(?:uick)?sort$/) {
  25             $^H{SORT} &= ~$sort::sort_bits;
  26             $^H{SORT} |=  $sort::quicksort_bit;
  27         } elsif ($_ eq '_mergesort') {
  28             $^H{SORT} &= ~$sort::sort_bits;
  29             $^H{SORT} |=  $sort::mergesort_bit;
  30         } elsif ($_ eq 'stable') {
  31             $^H{SORT} |=  $sort::stable_bit;
  32         } else {
  33             require Carp;
  34             Carp::croak("sort: unknown subpragma '$_'");
  35         }
  36     }
  37 }
  38
  39 sub current {
  40     my @sort;
  41     if ($^H{SORT}) {
  42         push @sort, 'quicksort' if $^H{SORT} & $sort::quicksort_bit;
  43         push @sort, 'mergesort' if $^H{SORT} & $sort::mergesort_bit;
  44         push @sort, 'stable'    if $^H{SORT} & $sort::stable_bit;
  45     }
  46     push @sort, 'mergesort' unless @sort;
  47     join(' ', @sort);
  48 }
  49
  50 1;
  51 __END__
  52
  53 =head1 NAME
  54
  55 sort - perl pragma to control sort() behaviour
  56
  57 =head1 SYNOPSIS
  58
  59     use sort 'stable';          # guarantee stability
  60     use sort '_quicksort';      # use a quicksort algorithm
  61     use sort '_mergesort';      # use a mergesort algorithm
  62
  63     use sort '_qsort';          # alias for quicksort
  64
  65     my $current = sort::current();      # identify prevailing algorithm
  66
  67 =head1 DESCRIPTION
  68
  69 With the sort pragma you can control the behaviour of the builtin
  70 sort() function.
  71
  72 In Perl versions 5.6 and earlier the quicksort algorithm was used to
  73 implement sort(), but in Perl 5.8 a mergesort algorithm was also made
  74 available, mainly to guarantee worst case O(N log N) behaviour:
  75 the worst case of quicksort is O(N**2).  In Perl 5.8 and later,
  76 quicksort defends against quadratic behaviour by shuffling large
  77 arrays before sorting.
  78
  79 A stable sort means that for records that compare equal, the original
  80 input ordering is preserved.  Mergesort is stable, quicksort is not.
  81 Stability will matter only if elements that compare equal can be
  82 distinguished in some other way.  That means that simple numerical
  83 and lexical sorts do not profit from stability, since equal elements
  84 are indistinguishable.  However, with a comparison such as
  85
  86    { substr($a, 0, 3) cmp substr($b, 0, 3) }
  87
  88 stability might matter because elements that compare equal on the
  89 first 3 characters may be distinguished based on subsequent characters.
  90 In Perl 5.8 and later, quicksort can be stabilized, but doing so will
  91 add overhead, so it should only be done if it matters.
  92
  93 The best algorithm depends on many things.  On average, mergesort
  94 does fewer comparisons than quicksort, so it may be better when
  95 complicated comparison routines are used.  Mergesort also takes
  96 advantage of pre-existing order, so it would be favored for using
  97 sort to merge several sorted arrays.  On the other hand, quicksort
  98 is often faster for small arrays, and on platforms with small memory
  99 caches that are much faster than main memory.  You can force the
 100 choice of algorithm with this pragma, but this feels heavy-handed,
 101 so the subpragmas beginning with a C<_> may not persist beyond Perl 5.8.
 102
 103 =cut
 104