Kurs:Algorithmen und Datenstrukturen/Kapitel 2/MergeSort/Perl

Aus Wikiversity

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!");
   }
 }