5 # The hints for pp_sort are now stored in $^H{sort}; older versions
6 # of perl used the global variable $sort::hints. -- rjh 2005-12-19
8 $sort::hint_bits = 0x04020000; # HINT_LOCALIZE_HH | HINT_HH_FOR_EVAL
10 $sort::quicksort_bit = 0x00000001;
11 $sort::mergesort_bit = 0x00000002;
12 $sort::sort_bits = 0x000000FF; # allow 256 different ones
13 $sort::stable_bit = 0x00000100;
21 Carp::croak("sort pragma requires arguments");
24 no warnings 'uninitialized'; # bitops would warn
26 while ($_ = shift(@_)) {
27 if (/^_q(?:uick)?sort$/) {
28 $^H{sort} &= ~$sort::sort_bits;
29 $^H{sort} |= $sort::quicksort_bit;
30 } elsif ($_ eq '_mergesort') {
31 $^H{sort} &= ~$sort::sort_bits;
32 $^H{sort} |= $sort::mergesort_bit;
33 } elsif ($_ eq 'stable') {
34 $^H{sort} |= $sort::stable_bit;
35 } elsif ($_ eq 'defaults') {
39 Carp::croak("sort: unknown subpragma '$_'");
42 $^H |= $sort::hint_bits;
49 Carp::croak("sort pragma requires arguments");
52 no warnings 'uninitialized'; # bitops would warn
53 while ($_ = shift(@_)) {
54 if (/^_q(?:uick)?sort$/) {
55 $^H{sort} &= ~$sort::sort_bits;
56 } elsif ($_ eq '_mergesort') {
57 $^H{sort} &= ~$sort::sort_bits;
58 } elsif ($_ eq 'stable') {
59 $^H{sort} &= ~$sort::stable_bit;
62 Carp::croak("sort: unknown subpragma '$_'");
70 push @sort, 'quicksort' if $^H{sort} & $sort::quicksort_bit;
71 push @sort, 'mergesort' if $^H{sort} & $sort::mergesort_bit;
72 push @sort, 'stable' if $^H{sort} & $sort::stable_bit;
74 push @sort, 'mergesort' unless @sort;
83 sort - perl pragma to control sort() behaviour
87 use sort 'stable'; # guarantee stability
88 use sort '_quicksort'; # use a quicksort algorithm
89 use sort '_mergesort'; # use a mergesort algorithm
90 use sort 'defaults'; # revert to default behavior
91 no sort 'stable'; # stability not important
93 use sort '_qsort'; # alias for quicksort
97 $current = sort::current(); # identify prevailing algorithm
102 With the C<sort> pragma you can control the behaviour of the builtin
105 In Perl versions 5.6 and earlier the quicksort algorithm was used to
106 implement C<sort()>, but in Perl 5.8 a mergesort algorithm was also made
107 available, mainly to guarantee worst case O(N log N) behaviour:
108 the worst case of quicksort is O(N**2). In Perl 5.8 and later,
109 quicksort defends against quadratic behaviour by shuffling large
110 arrays before sorting.
112 A stable sort means that for records that compare equal, the original
113 input ordering is preserved. Mergesort is stable, quicksort is not.
114 Stability will matter only if elements that compare equal can be
115 distinguished in some other way. That means that simple numerical
116 and lexical sorts do not profit from stability, since equal elements
117 are indistinguishable. However, with a comparison such as
119 { substr($a, 0, 3) cmp substr($b, 0, 3) }
121 stability might matter because elements that compare equal on the
122 first 3 characters may be distinguished based on subsequent characters.
123 In Perl 5.8 and later, quicksort can be stabilized, but doing so will
124 add overhead, so it should only be done if it matters.
126 The best algorithm depends on many things. On average, mergesort
127 does fewer comparisons than quicksort, so it may be better when
128 complicated comparison routines are used. Mergesort also takes
129 advantage of pre-existing order, so it would be favored for using
130 C<sort()> to merge several sorted arrays. On the other hand, quicksort
131 is often faster for small arrays, and on arrays of a few distinct
132 values, repeated many times. You can force the
133 choice of algorithm with this pragma, but this feels heavy-handed,
134 so the subpragmas beginning with a C<_> may not persist beyond Perl 5.8.
135 The default algorithm is mergesort, which will be stable even if
136 you do not explicitly demand it.
137 But the stability of the default sort is a side-effect that could
138 change in later versions. If stability is important, be sure to
143 The C<no sort> pragma doesn't
144 I<forbid> what follows, it just leaves the choice open. Thus, after
146 no sort qw(_mergesort stable);
148 a mergesort, which happens to be stable, will be employed anyway.
151 no sort "_quicksort";
152 no sort "_mergesort";
154 have exactly the same effect, leaving the choice of sort algorithm open.
158 As of Perl 5.10, this pragma is lexically scoped and takes effect
159 at compile time. In earlier versions its effect was global and took
160 effect at run-time; the documentation suggested using C<eval()> to
161 change the behaviour:
163 { eval 'use sort qw(defaults _quicksort)'; # force quicksort
164 eval 'no sort "stable"'; # stability not wanted
165 print sort::current . "\n";
167 eval 'use sort "defaults"'; # clean up, for others
169 { eval 'use sort qw(defaults stable)'; # force stability
170 print sort::current . "\n";
172 eval 'use sort "defaults"'; # clean up, for others
175 Such code no longer has the desired effect, for two reasons.
176 Firstly, the use of C<eval()> means that the sorting algorithm
177 is not changed until runtime, by which time it's too late to
178 have any effect. Secondly, C<sort::current> is also called at
179 run-time, when in fact the compile-time value of C<sort::current>
180 is the one that matters.
182 So now this code would be written:
184 { use sort qw(defaults _quicksort); # force quicksort
185 no sort "stable"; # stability not wanted
187 BEGIN { $current = print sort::current; }
190 # Pragmas go out of scope at the end of the block
192 { use sort qw(defaults stable); # force stability
194 BEGIN { $current = print sort::current; }