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