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