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