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