＊＊＊マージソート＊＊＊

さて、最終的な目標として少しおおきめのプログラムを提示します。このプログラムはマージソートといって要素を整列するプログラムです。

マージソートというアルゴリズムはクイックソートやヒープソートといった高速なソートと同じオーダーで整列できるアルゴリズムで連結リストが理解できたかどうかを確認するためにはちょうど良い材料でしょう。

必要となる知識は連結リストに関するものだけで良いので難しいものではありません。また、もちろんここで説明するものが連結リストを用いるのでその知識が必要になるのですが、配列を用いてマージソートを行う時は配列の知識があれば良いでしょう。

ではマージソートの説明をします。

まず、データ構造に対しどのような操作が基本的に必要になるのかを説明します。当然データがからの時は整列できないのでデータを登録する操作を行う必要があります。

この際第二部のように整列しながらデータを登録する必要はもちろんありません（これから整列するのですから）。連結リストの先頭にどんどん、登録していきましょう。

続いて連結リストを分割するという操作と、分割されたリストを結合するという操作が必要になります。マージソートではこれら二つの操作がメインになります。

次に実際にどのような方法でマージソートを行うのかを説明します。

先ほどもいった通り、マージソートで重要な操作はリストの分割と、結合です。

マージソートはリストを分割し、分割したリストをそれぞれ整列して、整列済みのリストをマージと呼ばれる作業で結合します。この際分割したここのリストを整列する時はマージソートの関数の再起呼び出しで整列します。

また、分割する時は単純にリストを二等分、または二等分に近い形で分割すれば良いでしょう。大切なのはマージと呼ばれる作業です。

マージとは整列済みの二つの要素の並び（配列、連結リストなど）を繋げる事によって整列済みの一つの要素の並びを作る作業を言います。

整列済みの数列A「２、９，１０」と数列B「１、３、６」をマージして数列C「１、２、３、６、９、１０」を生成する作業です。マージではまず数列AとBの先頭の要素を比較します。

そして小さいほうのデータを数列Cの先頭に持っていきます。

この時点で数列Aは「２，９，１０」、Bは「３、６」、Cは「１」となっています。そしてもう一度数列AとBの先頭の要素を比較して小さいほうのデータを数列Cの最後に挿入するわけです。

この時、数列Aは｢９，１０｣、Bは「３，６」、Cは「１，２」となります。

以上の作業を数列A、Bどちらかの要素が尽きるまで行います。そして片方の要素がなくなったらもう一方の全ての要素を数列Cの最後にそのままの順番で挿入していきます。これがマージです。

さて、このマージを利用してマージソートを行うのですが、とりあえず、マージソートはできるものとしてプログラムの疑似コーディングを行ってみましょう。

疑似コーディングとはプログラムの下書きの事です。図4-1-2を見て下さい。

このような手順でマージソートを行うのが普通でしょう。また、先ほども説明したように分割したリストをそれぞれ整列する時には再起呼び出しを用いるのでリストが空になったらreturnするように関数の先頭でその判定を行わなくてはなりません。

そのため引数にはソートすべきリストが空であるかどうかを判定できるようなものがふさわしいのですが、これを判定するには整列すべきリストの先頭を指すポインタがあれば十分です。従ってプログラムの概要は図４-１-３のようになります。

さて、一つ一つの細かいところを見ていきましょう。

まず、関数の引数です。ここにはあらかじめ定義したデータ型へのポインタ変数が入ります。ここではデータ型を図4-1-4のように定義します。そのため、この関数の引数は Name *x とする事にします。

次に連結リストが空であるか、または要素が一つしかないかを判定するためには if 文を用いてｘがNULLであるか x->next がNULLであるかで場合分けをすれば良いでしょう。

つまり、単純に if(x==NULL || x->next == NULL) と判定してやれば良いのです。もちろん、この判定の後に来るのは関数の終了(return)です。続いてリストの分割です。

リストはほぼ半分の大きさに分割されるように分割します。その際、連結リストを用いて分割するので、配列のように簡単に分割する事はできません。

ではどのように分割するのかというとまず、二つのポインタ変数を用意します。そして両方のポインタ変数を進めていき最終的に片方がリストの最後尾を指すようし、もう一つがリストのほぼ中間を指すようにすれば良いわけです。

なぜポインタ変数を二つ用い片方のポインタ変数に最後までリストを辿らせるかというと、このポインタが進む分の半分をもう一つのポインタが進めばもう一つのポインタはリストの中間を指すようになるからです。そのため、ポインタ変数が二つ必要になるのです。

最後にマージソートにおいて最も重要な部分マージについての具体的な説明を行います。

このマージは先ほども説明した通り、二つの整列済みのリストを併合し、新しい整列済みのソートにする作業です。この作業はそれを行う関数を作り実現させる事にします。

まず、関数の入力と出力を考える事にしましょう。

入力としては当然、二つの整列済みリストを渡す事になります。もちろん、これらはその先頭の要素へのポインタを渡せば良いので関数の入力は二つのポインタ変数によって表される事になります。

また、出力は完成した整列済みリストを返すのですから、こちらもリストの先頭へのポインタを返せば良い事になるでしょう。

つまり、関数の書式は Name *merge(Name *,Name *); となります。

次に関数の中身ですが、まず、二つのリストの先頭を比較して辞書式に先になるほうを新しいリストの先頭に持っていきます。

そのためにあらかじめ新しいリストの先頭のポインタ変数を用意しておきましょう。名前はｘとします。

そして二つのリストの先頭を比較し、新しいリストに入るべき要素はこの変数ｘに代入する事にしましょう。

そして代入したら新しく加えた要素は変数ｘの一つ前に持っていく事にします。

このようにして常に変数ｘは新しいデータの末尾を表すようにすればそこにデータを代入する事でどんどん、リストをマージしていく事ができます。

しかしながら、このように変数がリストの末尾を指している状態だと、関数は一体何を返せば良いのかが分かりません。そのためにもう一つの変数を用意してその変数に新しいリストの先頭を保存しておく事にします。

実際のプログラムは図4-1-5のようになります。

ここまでの事を踏まえて実際にマージソートを行うプログラムを記述してみると図4-1-6のようになります。