Download code

Jump to: navigation, search

Back to Merge_sort_(Perl)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

mergesort.perl

  1 #!/usr/bin/env perl
  2 # The authors of this work have released all rights to it and placed it
  3 # in the public domain under the Creative Commons CC0 1.0 waiver
  4 # (http://creativecommons.org/publicdomain/zero/1.0/).
  5 # 
  6 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  7 # EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  8 # MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  9 # IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 10 # CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 11 # TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 12 # SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 13 # 
 14 # Retrieved from: http://en.literateprograms.org/Merge_sort_(Perl)?oldid=6011
 15 
 16 
 17 use strict;
 18 use warnings;
 19 
 20 sub mergesort_string
 21 {
 22 	my ($aref, $begin, $end)=@_;
 23 
 24 	my $size=$end-$begin;
 25 
 26 	if($size<2) {return;}
 27 	my $half=$begin+int($size/2);
 28 
 29 	mergesort_string($aref, $begin, $half);
 30 	mergesort_string($aref, $half, $end);
 31 
 32 	for(my $i=$begin; $i<$half; ++$i) {
 33 		if($$aref[$i] gt $$aref[$half]) {
 34 			my $v=$$aref[$i];
 35 			$$aref[$i]=$$aref[$half];
 36 
 37 			my $i=$half;
 38 			while($i<$end-1 && $$aref[$i+1] lt $v) {
 39 				($$aref[$i], $$aref[$i+1])=
 40 					($$aref[$i+1], $$aref[$i]);
 41 				++$i;
 42 			}
 43 			$$aref[$i]=$v;
 44 		}
 45 	}
 46 }
 47 sub msort_string
 48 {
 49 	my $size=@_;
 50 	mergesort_string(\@_, 0, $size);
 51 }
 52 
 53 sub mergesort_number
 54 {
 55 	my ($aref, $begin, $end)=@_;
 56 
 57 	my $size=$end-$begin;
 58 
 59 	if($size<2) {return;}
 60 	my $half=$begin+int($size/2);
 61 
 62 	mergesort_number($aref, $begin, $half);
 63 	mergesort_number($aref, $half, $end);
 64 
 65 	for(my $i=$begin; $i<$half; ++$i) {
 66 		if($$aref[$i] > $$aref[$half]) {
 67 			my $v=$$aref[$i];
 68 			$$aref[$i]=$$aref[$half];
 69 
 70 			my $i=$half;
 71 			while($i<$end-1 && $$aref[$i+1] < $v) {
 72 				($$aref[$i], $$aref[$i+1])=
 73 					($$aref[$i+1], $$aref[$i]);
 74 				++$i;
 75 			}
 76 			$$aref[$i]=$v;
 77 		}
 78 	}
 79 }
 80 sub msort_number
 81 {
 82 	my $size=@_;
 83 	mergesort_number(\@_, 0, $size);
 84 }
 85 
 86 my @towns=qw(Paris London Stockholm Berlin Oslo Rome Madrid Tallinn Amsterdam Dublin);
 87 print "towns before mergesort:";
 88 foreach (@towns) {
 89 	print " $_"
 90 }
 91 print "\n";
 92 
 93 msort_string(@towns);
 94 print "towns after mergesort:";
 95 foreach (@towns) {
 96 	print " $_"
 97 }
 98 print "\n";
 99 
100 my @numbers=qw(9 8 6 98 43 12 59 52 4 5 14 2 92 3 32 54 22 41 7 34 15 3 1 13 99 42 63 34);
101 print "numbers before mergesort:";
102 foreach (@numbers) {
103 	print " $_"
104 }
105 print "\n";
106 
107 msort_number(@numbers);
108 print "numbers after mergesort:";
109 foreach (@numbers) {
110 	print " $_"
111 }
112 print "\n";


hijacker
hijacker
hijacker
hijacker

build.log

1 /tmp/litprog2774651/mergesort.perl syntax OK