Algorithms

inversion_count.pl

#!/usr/bin/env perl
use strict;
use warnings;
use feature qw( say );

# my @arr = ( 4, 2, 3, 6, 5, 7, 1,);
# my @arr = (1,3,5,2,4,6);

my $verbose = 1 if ($ARGV[0] && $ARGV[0] eq '-v');

my @arr;
while(my $line = <>) {
    chomp $line;
    push @arr, 0+$line;
}

debug( '--> original: ', join(', ', @arr), " <--");
debug( '-'x25 );
my $inv_count = sort_and_count(\@arr, $#arr+1);
say '='x25;
say "--> Total Inversion Count: $inv_count";
exit(0);

sub sort_and_count {
    my ($arr, $n) = @_;
    return ($arr, 0) unless $n > 1;

    my $mid = $n % 2 == 1 ? ($n-1)/2 : $n/2;
    my @left = @$arr[0..$mid-1];
    my @right = @$arr[$mid..$n-1];

    my ($sleft, $x)   = sort_and_count( \@left, $mid );
    my ($sright, $y)  = sort_and_count( \@right, $n-$mid);
    my ($merged, $z) = merge_and_countsplitinv( $sleft, $sright, $n );

    return ($merged, $x+$y+$z);
}

sub merge_and_countsplitinv {
    my ($left, $right, $n) = @_;
    debug(join(', ', @$left), ' --><-- ', join(', ', @$right));
    my ($l_c, $r_c) = ($#$left+1, $#$right+1);
    my ($i, $j) = (0, 0);
    my @merged;
    my $inv = 0;

    for my $k (0..$n-1) {
        if ($i<$l_c && $j<$r_c) {
            if ( $left->[$i] < $right->[$j]) {
                push @merged, $left->[$i];
                $i+=1;
            } else {
                push @merged, $right->[$j];
                $j+=1;
                $inv += $l_c - $i;
            }
        } else {
            if ($i>=$l_c) {
                push @merged, @$right[ $j..$#$right ];
            } else {
                push @merged, @$left[ $i..$#$left ];
            }
            last;
        }
    }

    debug(join(', ', @merged));
    debug("found $inv inversion(s)");

    return (\@merged, $inv);
}

sub debug {
    my @msg = @_;
    print @msg, "\n" if $verbose;
}