Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save Puriney/6082898 to your computer and use it in GitHub Desktop.
Save Puriney/6082898 to your computer and use it in GitHub Desktop.
PERL: Merge Sort Inverstion Times
our $invTimes =0;
sub mergeSortInversions{
my @x =@_;
return @x if (@x < 2);
my $mid = int (@x/2);
my @a = mergeSortInversions(@x[0 .. $mid - 1]);
my @b = mergeSortInversions(@x[$mid .. $#x]);
for (my $i = 0; $i < @x; $i++) {
if (!@a){
$x[$i]=shift @b;
}
elsif (!@b){
$x[$i]=shift @a;
}
elsif ($a[0]<=$b[0]){
$x[$i]=shift @a;
}
else {
$invTimes =$invTimes+@a;
$x[$i]=shift @b;
}
}
return(@x);
}
@array = mergeSortInversions(@array);
print "\n$invTimes\n";
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment