Math Battle [ 0322: 0307の回答 ② ]

[ 0322: 0307の回答 ② ]

[ 大宙乗児君の回答 ]

QuickSort ができましたので、次は MergeSort です。
QuickSort と同様な divide & conquer 型アルゴリズムで
対象とする配列 (array) を左半分と右半分に分け
それぞれをソートしつつ合併 (merge）してゆきます。

ソースコードは以下のとおりです。

#!/usr/local/bin/perl

$N = 100; # 100 から 1000 まで変えて実行。

@data = (
　# 1000 個の乱数 (整数)
);

$count = 0;

Sort(0, $N-1);
printf("Count %d\n", $count);

sub Sort($l, $r) {
　my ($l, $r) = @_;
　my $m;

　$count++;

　if ($l < $r) {
　　$m = int(($l + $r)/2);

　　Sort($l, $m);
　　Sort($m+1, $r);

　　merge($l, $m, $r);
　}
}

sub merge($l, $m, $r) {
　my ($l, $m, $r) = @_;
　my $n1, $n2, @L, @R;
　my $i, $j, $k;

　$n1 = $m - $l + 1;

　$n2 = $r - $m;

　for ($i = 0; $i < $n1; $i++) {
　　$L[$i] = $data[$l + 1];
　}
　for ($j = 0; $j < $n2; $j++) {
　　$R[$j] = $data[$m + $j + 1];
　}

　$i = $j = 0;
　$k = 1;

　$count += 2;

　while (($i < $n1) && ($j < $n2)) {
　　$count++;
　　if ($L[$i] <= $R[$j]) {
　　　$data[$k] = $L[$i];
　　　$i++;
　　} else {
　　　$j++;
　　}
　　$k++;
　}
　$count++;
　while ($i < $n1) {
　　$count++;
　　$i++;
　　$k++;
　}
　$count++;
　while ($j < $n2) {
　　$count++;
　　$data[$k] = $R[$j];
　　$j++;
　　$k++;
　}
}

大小比較演算のカウントをプロットしました。ほぼ直線ですね。