マージソート

perlのsort関数はマージソートを使っているということなので、
勉強のため、perlでマージソートするプログラムを書きました。

use strict;
use warnings;


{
    my @a = (8,4,3,9,7,6,5,2,1);
    print join(',',@a), "\n";
    print "===================\n";
    print join(',',sort(@a)), "\n";
}


#                                                                                              
# 二つの配列リファレンスを受け取って、並び替えながらマージする                                 
#                                                                                              

sub merge {
    my ($a1, $a2) = @_;

    my $i = 0;
    my $j = 0;

    my $a1_length = @$a1;
    my $a2_length = @$a2;

    my @new_a = ();

    while ($i < $a1_length || $j < $a2_length) {
        if ($j >= $a2_length || ($i < $a1_length && $a1->[$i] < $a2->[$j])) {
            $new_a[$i+$j] = $a1->[$i];
            $i++;
        } else {
            $new_a[$i+$j] = $a2->[$j];
            $j++;
        }
    }

    return @new_a;
}


#                                                                                              
# 一つの配列を受け取って、要素が2以上だったら二つの配列に分解して、それぞれの配列をマージソートする。                                                                                       
# マージソートされた二つの配列をマージする。                                                   
#                                                                                              

sub merge_sort {
    my @a = @_;

    my $a_length = @a;
    my @new_a = ();

    if ($a_length > 1) {
        my $m = $a_length / 2;
        my $n = $a_length - $m;

        my @a1 = ();
        my @a2 = ();

        for (my $i = 0; $i < $m; $i++) {
            $a1[$i] = $a[$i];
        }

        for (my $i = 0; $i < $n; $i++) {
            $a2[$i] = $a[$m+$i];
        }

        @a1 = merge_sort(@a1);
        @a2 = merge_sort(@a2);
        @new_a = merge(\@a1, \@a2);
    }

    return @new_a;
}


sub sort {
    my @a = @_;
    return merge_sort(@a);
}

マージソートの特徴として下記のようなものがあるみたいですね。

直接アクセスできないリスト構造でもソートを行なえる
一時的に大きなメモリ空間が必要
元データの状態によって性能が大きく変化しない(安定なソートアルゴリズム)
O(nlogn)
比較的高速なソート(クイックソートほどではない)

メメメモモ

プログラミング、筋トレ、ゲーム、etc

参考文献