Commit | Line | Data |
84d4ea48 |
1 | package sort; |
2 | |
045ac317 |
3 | our $VERSION = '1.01'; |
84d4ea48 |
4 | |
045ac317 |
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; |
84d4ea48 |
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; |
84d4ea48 |
16 | |
17 | use strict; |
18 | |
19 | sub import { |
20 | shift; |
21 | if (@_ == 0) { |
22 | require Carp; |
23 | Carp::croak("sort pragma requires arguments"); |
24 | } |
84d4ea48 |
25 | local $_; |
045ac317 |
26 | no warnings 'uninitialized'; # bitops would warn |
84d4ea48 |
27 | while ($_ = shift(@_)) { |
c53fc8a6 |
28 | if (/^_q(?:uick)?sort$/) { |
045ac317 |
29 | $hints &= ~$sort::sort_bits; |
30 | $hints |= $sort::quicksort_bit; |
c53fc8a6 |
31 | } elsif ($_ eq '_mergesort') { |
045ac317 |
32 | $hints &= ~$sort::sort_bits; |
33 | $hints |= $sort::mergesort_bit; |
c53fc8a6 |
34 | } elsif ($_ eq 'stable') { |
045ac317 |
35 | $hints |= $sort::stable_bit; |
84d4ea48 |
36 | } else { |
37 | require Carp; |
71c4de84 |
38 | Carp::croak("sort: unknown subpragma '$_'"); |
84d4ea48 |
39 | } |
40 | } |
41 | } |
42 | |
43 | sub current { |
44 | my @sort; |
045ac317 |
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; |
84d4ea48 |
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 | |
c53fc8a6 |
63 | use sort 'stable'; # guarantee stability |
64 | use sort '_quicksort'; # use a quicksort algorithm |
65 | use sort '_mergesort'; # use a mergesort algorithm |
84d4ea48 |
66 | |
c53fc8a6 |
67 | use sort '_qsort'; # alias for quicksort |
84d4ea48 |
68 | |
c53fc8a6 |
69 | my $current = sort::current(); # identify prevailing algorithm |
84d4ea48 |
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 |
c53fc8a6 |
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 |
b0ae2885 |
84 | input ordering is preserved. Mergesort is stable, quicksort is not. |
c53fc8a6 |
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. |
84d4ea48 |
106 | |
0e59b7c6 |
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 | |
84d4ea48 |
112 | =cut |
113 | |