出席の確認はOpenLMS の 3 限のコマを用いて行う． 3限の授業時間中に出席登録を完了せよ．
この授業のトップページから レポートのページに移動し， レポートの提出状況を常に確認せよ．
マージソートの計算量はO(n log n) であり，理論上の最速 のオーダーであるが定数係数が大きい． 配列のソートでは実用上はクイックソートに劣ることが多い． 安定なソートである，最悪時にもO(n log n) が保障される という理由などから採用されることも少なくない．
マージソートは要素の最初から順番にアクセスするシーケンシャル アクセスを行うことが特徴で，外部整列に向いている．
マージソートもクイックソートと同様，分割統治法による アルゴリズムである．一般に分割統治法では，以下の手順に 従って問題を解く．
クイックソートでは 2.1. で大きな仕事（分割）を行い， 2.3.では何も処理をしない．（あらかじめ枢軸を中心に分割 が行われているので，副問題が解けると枢軸の両側が整列され， 自動的に全体の配列が整列済みになる）
マージソートでは逆に 2.1. の仕事がほとんどなく（中間で配列を2本に分けるだけ）， 2.3. で大きな仕事（マージ）を行う．
マージソートの中心的な操作がマージである． マージの目的も操作も直感的に理解しやすい． マージの入力は 2 本の整列済みの配列で，出力は それを合成して作成した 1 本の大きな整列済みの配列である． アルゴリズムも自然なもので，2 本の入力配列の 先頭同士から順に比較し，勝者を取り出して出力配列へ 格納することを繰り返すものである（p.219 Fig 15.2)． 疑似コードにしたものが p.218 Fig15.1 である． 入力配列のどちらかが先に無くなった場合，残ったほうの 入力配列の残りの要素を無条件に出力配列に詰める操作が 必要なことに注意する．
マージソートのアルゴリズムを分割統治法の手順に従って書くと 以下のようになる．
これをそのまま疑似コードにしたものが p.220 Fig15.3 である．
p.223 List 15.1 は「Fig. 15.3 の疑似コードを忠実にコーディングした」 と書いてあるものの，x と y をマージする部分で 巧妙なテクニックを用いているので注意が必要である． マージの疑似コードは p.218 Fig. 15.1 に掲載されている． Fig. 15.1 では最後に入力配列 a, b のうちどちらかの要素を使い尽くしたあと， 残った配列の要素を c に詰める処理が明記されているが， List 15.1 のコードにはこれにあたる処理が明記されていない． この理由を以下で説明する．
分割統治法に沿って説明すると，最初の入力配列の大きさが n であれば 真ん中で分割して大きさ n/2 の配列 2 個に分割して，それぞれを 整列することを副問題とする．n が奇数の場合は大きさ (n-1)/2+1 の配列と 大きさ (n-1)/2 の配列に分割する．（List 15.1 の 18 行目，mid の値に注目せよ． 前半の配列がa[low]からa[mid], 後半の配列が a[mid+1]からa[high]になる）
前半のa[low]からa[mid], 後半の a[mid+1]からa[high]をそれぞれ 再帰呼出しを使って整列する． 分割した 2 個の配列の大きさの和は low から high の間の要素数 high - low + 1 個 と同じである．もちろんマージした結果の要素数も high - low + 1 個である．
配列によるマージソートである List 15.1 では作業領域として 入力配列 a と同じサイズの配列 b を用いる．これに一旦 入力配列を分割したものをコピーし，そこからマージ処理を 行いながら配列 a にマージした結果の配列を格納する．
入力配列 a を分割した 2 つの部分配列を b にコピーするとき， 前半の a[low] から a[mid] はそのままの位置で b[low] から b[mid] にコピーする（List15.1 27-28行）．しかし 後半の a[mid+1] から a[high] は b の同じ範囲に逆順に コピーする（List15.1 31-32行，p.225 Fig 15.5参照）．
こうして作った配列 b について，前の部分列については ポインタ添字 i を左端の low から右へ向かって動かし， 後の部分列についてはポインタ添字 j を右端の high から左に動かす．最大値が必ず前の部分列と後の部分列の 境界に存在するのでそれを番兵として利用し，添字の 動く範囲を正しく制限するというテクニックを利用している． このため，前の部分列，後の部分列の片方が終わった後の 処理は必要ない．
p.223 List15.1 を 練習10.1 の追加と同様のことを行って動作させる． merge_sort_array 関数の引数は，1.配列名，2.ソート範囲の最初の添字， 3.ソート範囲の最後の添字，となっているため， これまでの他のソートと入出力の仕様をあわせる ためだけの関数 merge_sort も作成する．
具体的にはList 15.1 の
#define MAX_ELEMENTS 10000
図12.1 List15.1 の define 文
の前に以下の include 文を挿入し，
#include <stdio.h>
図12.2 追加する include 文
同じ define の後に以下のプロトタイプ宣言を挿入する．
void merge_sort_array(int a[], int low, int high); void merge_sort(int a[], int n); void print_array(int a[], int n);
図12.3 追加するプロトタイプ宣言
後はプログラムの末尾に merge_sort関数, print_array 関数と main 関数を記述すればよい． この部分は以下のようになる． main を書き換えてテスト実行せよ．
void merge_sort(int a[], int n)
{
merge_sort_array(a, 0, n - 1);
}
void print_array(int a[], int n)
{
int i;
for (i = 0; i <= n - 1; i++){
printf("%2d ", a[i]);
}
printf("\n");
}
int main(void)
{
int data[10];
data[0]=20;
data[1]=6;
data[2]=55;
data[3]=74;
data[4]=3;
data[5]=45;
data[6]=13;
data[7]=87;
data[8]=46;
data[9]=30;
print_array(data, 10);
merge_sort(data, 10);
print_array(data, 10);
}
図12.4 追加する merge_sort, print_array, main 関数
p.222 Fig15.4 のように最初に分割が行われ，長さ1の配列まで分割 された後，マージが行われる．一回の分割で長さが半分になるので 分割とマージはそれぞれ log n 回行われる．
配列によるマージソートでは分割1回の手間は O(1)， Fig15.4 の1段あたりの分割回数は高々n/2なので1段あたりの の計算量は O(n)である． 連結リストによるマージソートでも O(n) となる．
マージについては Fig15.4 の 1 段階あたり O(n) の計算量になる．
2 log n 段階それぞれに O(n) の計算量が必要なので マージソートの計算量は O(n log n) すなわち比較を 利用した整列アルゴリズムの下限を達成している．
クイックソートと比較すると，マージソートは 最悪時でも O(n log n)が保証されるという利点があるが， 定数係数部分で劣っている．具体的には 整列対象の配列と同じ大きさの配列に毎回コピーする 手間が問題になる．
計算速度の面だけでなく，使用メモリ量という面でもこの データのコピーは問題になる．クイックソートの作業領域の 大きさが O(log n) であるのに対してマージソートでは O(n) すなわち整列すべき領域と同じだけの作業領域を要する．
要素の値が等しい時に前の部分列を優先することで 安定な整列ができることはマージソートの利点である．
マージソートは連結リストを用いた実装に向いている． 連結リストを用いればマージソートの問題点である 各要素を作業用の領域に一旦コピーする，という作業を 回避できる．
p.229 List15.2 がマージソートの連結リスト版である． もともとマージ操作は二つのリストの先頭から順に 勝ち負けを比較するアルゴリズムなのでそのまま 連結リストで実装できる．こちらのプログラムのほうが p.218 Fig 15.1 の疑似コードに近い．
p.231 Fig 15.6 はポインタ a が指す(a を先頭要素のアドレスとする）連結リストと b が指す連結リストをマージして head->next が指す連結リストにする 作業を説明するものである．
分割では中央の要素のポインタを知る必要がある．List15.2 71-76行目では1個づつ進むポインタ a と 2 個づつ進むポインタ b を使い，b が連結リストの終わりに来たときに a が中央を 指している，ということを利用して中央のポインタを得ている．
連結リストではランダムアクセスが出来ないため， クイックソートを用いる場合は枢軸が最悪の値になるのを 避ける効率的な方法がない．このため，連結リストの整列には マージソートの方が適していると言える．
主記憶上のデータを整列することを内部整列， 外部記憶上のデータを整列することを外部整列という．
外部記憶は主記憶に比べて
という特徴がある．
マージソートでは，主記憶に入る分量だけ順次読み込んで，それ以外は 外部記憶に置いたままソートすることができる．p.235 Fig 15.7 は主記憶には 2 個の要素しか同時に置けないとした場合の 処理を示している．
マージソートでは利用できるテープの本数に合わせた 整列方法をとることができる．
次回のコンテンツの「ヒープソート」の16.1.3までは今回説明する．
第 12 回課題「最大値の計算」 を提出せよ．