Commit | Line | Data |
---|---|---|
84d4ea48 JH |
1 | package sort; |
2 | ||
045ac317 | 3 | our $VERSION = '1.01'; |
84d4ea48 | 4 | |
045ac317 RGS |
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 JH |
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 JH |
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 RGS |
29 | $hints &= ~$sort::sort_bits; |
30 | $hints |= $sort::quicksort_bit; | |
c53fc8a6 | 31 | } elsif ($_ eq '_mergesort') { |
045ac317 RGS |
32 | $hints &= ~$sort::sort_bits; |
33 | $hints |= $sort::mergesort_bit; | |
c53fc8a6 | 34 | } elsif ($_ eq 'stable') { |
045ac317 | 35 | $hints |= $sort::stable_bit; |
84d4ea48 JH |
36 | } else { |
37 | require Carp; | |
71c4de84 | 38 | Carp::croak("sort: unknown subpragma '$_'"); |
84d4ea48 JH |
39 | } |
40 | } | |
41 | } | |
42 | ||
43 | sub current { | |
44 | my @sort; | |
045ac317 RGS |
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 JH |
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 JH |
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 JH |
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 JH |
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 JH |
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 RGS |
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 JH |
112 | =cut |
113 |