This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
Implement the sort pragma. Split sort code from pp_ctl.c
[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;
11$sort::insensitive_bit = 0x00000200;
12$sort::safe_bits = 0x00000300;
13$sort::fast_bit = 0x00000400;
14
15use strict;
16
17sub import {
18 shift;
19 if (@_ == 0) {
20 require Carp;
21 Carp::croak("sort pragma requires arguments");
22 }
23 $^H |= $sort::hint_bits;
24 local $_;
25 while ($_ = shift(@_)) {
26 if (/^q(?:uick)?sort$/) {
27 $^H{SORT} &= ~$sort::sort_bits;
28 $^H{SORT} |= $sort::quicksort_bit;
29 return;
30 } elsif ($_ eq 'mergesort') {
31 $^H{SORT} &= ~$sort::sort_bits;
32 $^H{SORT} |= $sort::mergesort_bit;
33 return;
34 } elsif ($_ eq 'safe') {
35 $^H{SORT} &= ~$sort::fast_bit;
36 $^H{SORT} |= $sort::safe_bits;
37 $_ = 'mergesort';
38 redo;
39 } elsif ($_ eq 'fast') {
40 $^H{SORT} &= ~$sort::safe_bits;
41 $^H{SORT} |= $sort::fast_bit;
42 $_ = 'quicksort';
43 redo;
44 } else {
45 require Carp;
46 Carp::croak("sort: unknown subpragma '@_'");
47 }
48 }
49}
50
51sub current {
52 my @sort;
53 if ($^H{SORT}) {
54 push @sort, 'quicksort' if $^H{SORT} & $sort::quicksort_bit;
55 push @sort, 'mergesort' if $^H{SORT} & $sort::mergesort_bit;
56 push @sort, 'safe' if $^H{SORT} & $sort::safe_bits;
57 push @sort, 'fast' if $^H{SORT} & $sort::fast_bit;
58 }
59 push @sort, 'mergesort' unless @sort;
60 join(' ', @sort);
61}
62
631;
64__END__
65
66=head1 NAME
67
68sort - perl pragma to control sort() behaviour
69
70=head1 SYNOPSIS
71
72 use sort 'quicksort';
73 use sort 'mergesort';
74
75 use sort 'qsort'; # alias for quicksort
76
77 # alias for mergesort: insenstive and stable
78 use sort 'safe';
79
80 # alias for raw quicksort: sensitive and nonstable
81 use sort 'fast';
82
83 my $current = sort::current();
84
85=head1 DESCRIPTION
86
87With the sort pragma you can control the behaviour of the builtin
88sort() function.
89
90In Perl versions 5.6 and earlier the quicksort algorithm was used to
91implement sort(), but in Perl 5.8 the algorithm was changed to mergesort,
92mainly to guarantee insensitiveness to sort input: the worst case of
93quicksort is O(N**2), while mergesort is always O(N log N).
94
95On the other hand, for same cases (especially for shorter inputs)
96quicksort is faster.
97
98In Perl 5.8 and later by default quicksort is wrapped into a
99stabilizing layer. A stable sort means that for records that compare
100equal, the original input ordering is preserved. Mergesort is stable;
101quicksort is not.
102
103The metapragmas 'fast' and 'safe' select quicksort without the
104stabilizing layer and mergesort, respectively. In other words,
105'safe' is the default.
106
107Finally, the sort performance is also dependent on the platform
108(smaller CPU caches favour quicksort).
109
110=cut
111