マージソートを実装

use strict;
use warnings;
use utf8;
use Data::Dumper;
use Time::HiRes qw(gettimeofday tv_interval);
binmode(STDOUT, ":utf8");

&main;

sub main {
    my $t0 = [gettimeofday];

    my $arr_size = 10;
    my @arr_elements = (8, 5, 9, 2, 6, 3, 7, 1, 10, 4);
    &merge_sort(\@arr_elements, $arr_size, 0, $arr_size);

    $\="\n";
    print @arr_elements;
    my $timer = tv_interval($t0) * 1000;
    print "$timer ms";
}

sub merge_sort {
    my ($arr_elements, $arr_size, $left, $right) = @_;
    
    if ($left + 1 < $right ) {
        my $mid = ($left + $right) / 2;
        &merge_sort($arr_elements, $arr_size, $left, $mid);
        &merge_sort($arr_elements, $arr_size, $mid, $right);
        
        $left = int $left;
        $right = int $right;
        $mid = int $mid;

        &merge($arr_elements, $arr_size, $left, $mid, $right);
    }
}    


sub merge {
    my ($arr_elements, $arr_size, $left, $mid, $right) = @_;
    
    my $n1 = $mid - $left;
    my $n2 = $right - $mid;
    
    my @left_arr;
    my @right_arr;

    for (my $i = 0; $i < $n1; $i++) {
        $left_arr[$i] = $arr_elements->[$left + $i]; 
    }
    for (my $i = 0; $i < $n2; $i++) {
        $right_arr[$i] = $arr_elements->[$mid + $i]; 
    }
    
    my $i = 0;
    my $j = 0;
    
    $left_arr[$n1] = 10000;
    $right_arr[$n2] = 10000;
    
    for (my $k = $left; $k < $right; $k++) {
        
        if ($left_arr[$i] <= $right_arr[$j]) {
            $arr_elements->[$k] = $left_arr[$i++];
        } else {
            $arr_elements->[$k] = $right_arr[$j++];
        }
    }
}

要素数3の配列をどう処理するかでかなりの時間を労した。いきなり要素数10の配列で試すのではなく、初めは要素数3の配列で試したりすることで問題を細かく切り分けて考えるのが大事だという教訓を得た。

「初めに配列を要素が1になるように分割して...」っていう解説がよくされているけど実際は添字足したり割ったりしているだけで要素1の配列を実際に作っているわけではない。