Kurs:Algorithmen und Datenstrukturen/Kapitel 2/MergeSort/Perl
Eine Implementation des MergeSort-Algorithmus als Perlmodul "MergeSort.pm" könnte folgendermaßen aussehen:
#!/usr/local/bin/perl -w
use strict;
sub new{
bless ({},ref($_[0]) || $_[0]);
}
sub sort{
my ($self, $a) = @_; # Referenz zum Original-Array
my $b = [@$a]; # Kopie des Arrays
$self->mergesort($b,$a,0,$#$a);
}
sub mergesort{
my ($self, $src, $dest, $von, $bis) = @_;
if ($bis == $von){
$dest->[$von] = $src->[$von];
}elsif($bis-$von==1){
if($src->[$bis] lt $src->[$von]){
($dest->[$von],$dest->[$bis])=($src->[$bis],$src->[$von]);
}else{
($dest->[$von],$dest->[$bis])=($src->[$von],$src->[$bis]);
}
}elsif($bis-$von>1){
my $mitte = $von + int(($bis-$von)/2);
$self->mergesort($dest,$src,$von,$mitte);
$self->mergesort($dest,$src,$mitte+1,$bis);
my ($i,$j,$k) = ($von,$mitte+1,$von);
while( $i <= $mitte && $j <= $bis){
$dest->[$k++] = $src->[($src->[$i] lt $src->[$j])?$i++:$j++];
}
while( $i <= $mitte ){ $dest->[$k++] = $src->[$i++]; }
while( $j <= $bis ){ $dest->[$k++] = $src->[$j++]; }
}else{
die("bis=$bis ist kleiner als von=$von!");
}
}