「ソートされている」とは……
まず、「昇順にソートされた状態」とはどんな状態のことでしょうか。
“任意に選んだデータが、それよりうしろに並んだデータより大きくない”が常に成り立つ
あるいはこう言い換えてもいいでしょう:
どのデータであっても、その次のデータより大きくない
つまりはi = 0..データ数-2に対しdata[i] <= data[i+1]が成り立つ、ということです。冒頭のバブル・ソートではこの条件を満たさない、つまり data[i] > data[i+1] であるとき両者を交換することを繰り返すアルゴリズムです。
少量のデータについて考えてみましょう。0から9までの10個のデータをかき混ぜて並べてみました:
8 1 9 2 0 5 7 3 4 6
このデータ列において、順序の反転している箇所に|を書き加えます。
8|1 9|2|0 5 7|3 4 6
|で区切られたいくつかのデータ列ができました。それぞれのデータ列内は昇順にソートされています。この“昇順にソートされたデータ列”を「連（run）」と呼ぶことにしましょう。
この例ではデータ列全体は5つの連で構成されています。これがソートされると:
0 1 2 3 4 5 6 7 8 9
となり、連を区切る|がなくなります。つまり連の数が1ってことです。
連の数が1であることが「ソートされた状態」と言ってもいいでしょうね。
「マージ」とは
マージ・ソートのキモとなる戦略は、2本の連を1本の連にまとめる（併合:merge）ことにあります。
さきほどの例「8|1 9|2|0 5 7|3 4 6」で先頭の二つの連「8」と「1 9」を一本の連にまとめると「1 8 9」となります。さらにその次の二本「2」と「0 5 7」をまとめると「0 2 5 7」となります。
このように、二本の連をまとめて一本の連とすることができれば、全体では「1 8 9|0 2 5 7|3 4 6」となり、連の数が5から3に減りました。もう一度繰り返すと「0 1 2 5 7 8 9|3 4 6」、さらにもう一度やれば「0 1 2 3 4 5 6 7 8 9」となってソート完了です。
2本の連を1本にマージすることで、データ列中の連の数はおよそ半分になります。この作業を繰り返して連の数を1にするのがマージ・ソートのアルゴリズムです。
