8140a7d2905e7388853a51d72d6414b9b831fb44
[p5sagit/p5-mst-13.2.git] / 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