最終的にFord-Johnson algorithmのMerge-insertion sortができることが目標

マージソート、インサートソート、バイナリインサートソートを順番に勉強して、最後にマージインサートソートにたどりつく、はず。

最後の方は、説明が投げ出し気味ですが、ご了承ください。。

*1) The art of computer programming 3 (second edition)
*2) ソートを極める！〜なぜソートを学ぶのか〜

なお、マージインサートソートのコードは載せておりません。

マージソート(Merge Sort)

マージとは、2つ以上のソート済みファイル（集合のこと）を結合して、1つのソート済みファイルを作成することを意味する。　
たとえば、[503 703 765] と　[087 512 677]
という2つのソート済みファイルをマージすると、
[087 503 512 677 703 765]というファイルになる。 *1)

これはそれぞれのファイルの最も小さな項目同士を比較して小さい方を出力する過程を繰り返す、という単純な方法で実現できる。

マージソートはいくつかの派生（？）アルゴリズムを持つようだが詳細は割愛

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

#define SIZE_DATA 15

template <typename T>
bool compairVec(std::vector<T>& vec1, std::vector<T>& vec2)
{
	if (vec1.size() != vec2.size())
		return (false);
	for (typename std::vector<T>::size_type i = 0; i < vec1.size(); ++i)
	{
		if (vec1[i] != vec2[i])
			return (false);
	}
	return (true);
}

// 2つの要素の集合(それぞれはソート済み)を、ソートしながら(仮想的に)マージする。
// result: 2つの要素の集合を含む配列。マージした結果もここに格納される。
// startLeft: result配列の中で、1つ目の要素の集合の開始インデント。
// middle: result配列の中で、1つ目の要素の集合の終了インデント。かつ +1 で2つ目の要素の集合の開始インデントとなる。
// endRight: result配列の中で、2つ目の要素の集合の終了インデント。
template <typename T>
void mergeVector(std::vector<T>& result, unsigned int startLeft, unsigned int middle, unsigned int endRight)
{
	// 1つ目の要素の集合（vecLeft）と2つ目の要素の集合（vecRight）をそれぞれresultからコピーする。それぞれの集合はソート済みである。（集合の要素が1つの場合もある）
	std::vector<T> vecLeft(result.begin() + startLeft, result.begin() + middle + 1);//2つめの引数の+1が意味するのは、最後の要素の次の要素(≒end())
	std::vector<T> vecRight(result.begin() + middle + 1, result.begin() + endRight + 1);

	unsigned int iLeft = 0; // vecLeftを走査するためのインデックス
	unsigned int iRight = 0; // vecRightを走査するためのインデックス
	unsigned int index = startLeft; // resultにデータを書き込むためのインデックス
	// vecLeft or vecRightを走査し終わるまで、それぞれのインデックスの要素を比較
	while (iLeft < vecLeft.size() && iRight < vecRight.size())
	{
		if (vecLeft[iLeft] <= vecRight[iRight])
			result[index++] = vecLeft[iLeft++]; //vecLeftの要素の方が小さければresultに挿入。そしてvecLeftを走査するインデックスをインクリメント
		else
			result[index++] = vecRight[iRight++];
	}

	// vecLeftが走査し終わっていなければ、vecLeftの残りの要素をresultに挿入
	while (iLeft < vecLeft.size())
		result[index++] = vecLeft[iLeft++];
	// vecRight 〃
	while (iRight < vecRight.size())
		result[index++] = vecRight[iRight++];
}

//要素の集合を再帰的に分割する
//vec: マージソートを行う要素の配列で、分割や併合は発生しないのでいつも同じベクターを参照している。
//left: vecを（仮想的に）分割した集合の左端のインデント
//right: vecを（仮想的に）分割した集合の右端のインデント
template <typename T>
void mergeSort(std::vector<T>& vec, unsigned int left, unsigned int right)
{
	if (left < right) // left == rightになった時は、要素が1つになっているので、それ以上は分割しない
	{
		// leftとrightの中間地点のインデックスを求める。
		// middleを利用することで、①集合を半分ずつに分割し、②分割した集合をマージするときの集合間の目印とする
		unsigned int middle = left + (right - left) / 2;

		mergeSort(vec, left, middle);//集合の左半分を、再帰的に（仮想）分割する
		mergeSort(vec, middle + 1, right);// 〃 右半分 〃

		// ここにきたとき、要素（left - right + 1）は2つ以上で、かつmiddleを境にソートされた集合になっている。
		mergeVector(vec, left, middle, right);
	}
}

int main(int ac, char **av)
{
	std::srand((unsigned int) std::time(NULL));

	std::vector<unsigned int> before;//ソートしたい元データ
	for (int i = 0; i < SIZE_DATA; ++i)//元データにランダムな数値を挿入
		before.push_back(std::rand());
	
	//元データを出力
	std::cout << "Before sort: " << std::endl;
	for (int i = 0; i < SIZE_DATA; ++i)
		std::cout << before[i] << " ";
	std::cout << std::endl;

	//自作マージソートのために、元データをコピー
	std::vector<unsigned int> copyVec1(before);
	//自作マージソートの実行
	mergeSort(copyVec1, 0, copyVec1.size() - 1);

	//ソート後のデータを出力
	std::cout << "After sort: " << std::endl;//元データを出力
	for (int i = 0; i < SIZE_DATA; ++i)
		std::cout << copyVec1[i] << " ";
	std::cout << std::endl;

	//マージソートが正しく実行できているかを確認するために、std::sortで元データをソート
	std::vector<unsigned int> copyVec2(before);
	std::sort(copyVec2.begin(), copyVec2.end());

	//自作ソートと、std::sortの結果を比較
	if (compairVec(copyVec1, copyVec2))
	{
		std::cout << "success" << std::endl;
		return (EXIT_SUCCESS);
	}
	else
	{
		std::cout << "fail" << std::endl;
		return (EXIT_FAILURE);
	}
}

インサートソート（挿入ソート, Insertion Sort）

インサートソートとは、整列してある配列に、新たな追加要素を、適切な場所に挿入するというアルゴリズムです。
以下に、単純なインサートソートの例を示します。

画像はwikiより
◆上記のアルゴリズムを簡単に解説
1回目のループ終了時：[4 8]が「整列している配列」で、[3]が「新たな追加要素」です。このとき8と3をまず比較して、3の方が小さいので、配列の要素を入れ替えます。続けて、4と3を比較して、3の方が小さいので、配列の要素を入れ替えます。（2回目のループ終了時になる）
（少しスキップして）
6回目のループ終了時：[2 3 4 5 6 7 8]が「整列している配列」で、[1]が「新たな追加要素」です。このとき8と1をまず比較して、1の方が小さいので、配列の要素を入れ替えます。続けて、7と1を比較して、1の方が小さいので、配列の要素を入れ替えます。これを5〜2の間も繰り返します。（7回目のループ終了時になる：1を挿入するために7回の比較が必要）

解説は以上です。

コード例は以下のようになります。

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

#define SIZE_DATA 15

template <typename T>
bool compairVec(std::vector<T>& vec1, std::vector<T>& vec2)
{
// meargeSortと変わらないので省略
}

template <typename T>
void insertionSort(std::vector<T>& vec)
{
	// 要素を1つづつ走査（i）
	for (typename std::vector<T>::size_type i = 1; i < vec.size(); ++i)
	{
		// vec[i]と、それより前方にある要素を比較するためのインデックス(j)
		typename std::vector<T>::size_type j = i;
		// 1つ前方の要素と比較し、前方の方が大きければswapする
		while (j > 0 && vec[j - 1] > vec[j])
		{
			std::swap(vec[j - 1], vec[j]);
			--j; // インデックスをデクリメントして、次はさらに前の要素と比較する
		}
	}
}

int main(int ac, char **av)
{
// meargeSortと変わらないので省略
}

上記の例では、比較が28回発生します。これは次に説明するバイナリインサートソートとの良い比較になります。

＊インサートソートは、マージインサーションソートでは利用しません。

バイナリインサートソート（2分探索挿入ソート；Binary insertion sort）

マージインサートソートでも利用されているので、理解は必須です。

こちらもインサートソートですが、最悪の場合の比較回数が少なくなるようなアルゴリズムになっています。
単純なインサートソートでは28回の比較を必要としていましたが、2分探索では17回の比較で済みます。

画像はwikiより
◆上記のアルゴリズムを簡単に解説
ポイントは、「すでに整列しているなら、整列している半分(らへん)の数値と比較する」を繰り返すというところ。

1回目のループ終了時：[4 8]が「整列している配列」で、[3]が「新たな追加要素」です。このとき8と3をまず比較して、3の方が小さい、とわかります。続けて、4と3を比較して、3の方が小さいので、配列に要素を挿入します。（2回目のループ終了時になる）
（少しスキップして）
6回目のループ終了時：[2 3 4 5 6 7 8]が「整列している配列」で、[1]が「新たな追加要素」です。このとき”整列している半分(らへん)の数値”である5と1をまず比較して、1の方が小さいので、次は4以下の要素と比較すれば良いことがわかります。続けて、”整列している半分(らへん)の数値”である3と1を比較して、1の方が小さいので、2以下の要素と比較すれば良いことがわかります。最後に2と1を比較して、1の方が小さいので、2の前に1を挿入します。（7回目のループ終了時になる：1を挿入するために3回の比較で済んだ）

このように、整列している半分らへんの数値と比較することで、最悪の場合の比較回数が減少します。

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

#define SIZE_DATA 15

template <typename T>
bool compairVec(std::vector<T>& vec1, std::vector<T>& vec2)
{
// meargeSortと変わらないので省略
}

template <typename T>
const typename std::vector<T>::const_iterator recursiveSearchInsertPos(const typename std::vector<T>::const_iterator begin,
	const typename std::vector<T>::const_iterator end, const T targetVal)
{
	if (begin == end)
		return (begin);
	else if ((end - begin) == 1)
	{
		if (targetVal < *begin)
			return (begin);
		else
			return (begin + 1);
	}
	else
	{
		const typename std::vector<T>::const_iterator middle = begin + ((end - begin) / 2);
std::endl;
		if (targetVal < *middle)
			return (recursiveSearchInsertPos<T>(begin, middle, targetVal));
		else
			return (recursiveSearchInsertPos<T>(middle + 1, end, targetVal));
	}
}

template <typename T>
void binarySearchInsertionSort(std::vector<T>& vec)
{
	for (typename std::vector<T>::size_type index = 1; index < vec.size(); ++index)
	{
		T valueToMove = vec[index];
		const typename std::vector<T>::const_iterator insertPos = recursiveSearchInsertPos<T>(vec.begin(), vec.begin() + index, valueToMove);
		vec.erase((vec.begin() + index));
		vec.insert(insertPos, valueToMove);
	}
}

int main(int ac, char **av)
{
// meargeSortと変わらないので省略
}

マージインサートソート (Merge insertion sort, Ford-Johnson algorithm)

wikiにも詳細はありますが、いかんせん絵としての理解が難しいので、描いてみました。
5つの要素があるとした時、マージインサートソートはどのように動作するのか?

要素の最初の並び： 5 3 4 2 1
↓ 要素が2つのペアを作る（Group the elements of X into [n/2] pairs of elements）

[5 3][4 2] 1

↓ ペア内でソートする(Perform [n/2] comparisons, one per pair, to determine the larger of the two elements in each pair.)

[3 5][2 4] 1

↓ ペア内の大きい方の数値を取り出す

5 4　　//先ほどペアだった数値(5には3、4には2）が紐づいている。
// このとき、５に紐づいている数値は１つなので、サイズ２の状態とする

↓ 要素が2つのペアを作る(Recursively sort the [n/2] larger elements from each pair, creating a sorted sequence S of [n/2] of the input elements, in ascending order.)

[5 4] //サイズ２の状態

↓ ペア内でソートする(同上)

[4 5]　//ペアだった数値も一緒に移動する(同上)

↓ ペア内の大きい方の数値を取り出す(同上)

5　//先ほどペアだった数値(5には4）が紐づいているようにする
//このとき、5に紐づいている数値は3つ（3, 4, 2）なので、サイズ４の状態とする

↓ 要素が2つのペアを作る(同上)

[5 -] //サイズ４の状態。ペアが作れないので、再帰は終了

↓ ペア要素を展開する

[5] //サイズ２の状態
 ↑
[4] //サイズ２
//サイズ２の状態を持つ数値は、5と４の２つだけなので、サイズ２のソート（並び替え）は完了した

↓ ペア要素を展開する

[4] → [5] //全てサイズ１の状態になる
 ↑     ↑
[2]   [3]  [1]
//このとき、４とペアだった２は、４よりも必ず小さくなる。
//そのため、[2] → [4] → [5]は並び替えが完了している。

↓ ペア要素を挿入する(Insert the remaining [n/2] -1 elements of X\S into S, one at a time, with a specially chosen insertion ordering described below. Use binary search in subsequences of S(as described below) to determine the position at which each element should be inserted.)

[2] → [4] → [5]
             ↑
            [3]  [1]
//この時に、ソートされていない要素[3]&[1]を
// ①どんな順番で ②どのように挿入場所を決定するか がミソ

②は、バイナリインサートを利用します。
①は、バイナリインサートが効率的な回数に収まるように、[1]を先に挿入します。

②については、整列した要素に、新しい要素を挿入する時に、バイナリインサートを利用すると比較回数が少なくなることは、バイナリインサートソートで実例を用いて説明しました。

①については、上記の例を用いて、理論ではなく実例でまずは理解しましょう。

正解の挿入順

正解の挿入順では、比較回数は４回です。

[2] → [4] → [5]
             ↑
            [3]  [1]
//整列した要素[2][4][5]に、新しい要素[1]を挿入すると、
//バイナリインサートでは最初に[4]と比較、次に[2]と比較して、
//計２回の比較で挿入場所を決定できます。

[1] → [2] → [4] → [5]
                   ↑
                  [3]
//整列した要素[1][2][4][5]に、新しい要素[3]を挿入します。
//このとき、[3]は[5]よりも必ず小さいので、整列した要素[1][2][4]
//と比較すればいいですね。([5]を比較対象から除外できる)
//すると、バイナリインサートでは最初に[2]と比較、次に[4]と比較して、
//計２回の比較で挿入場所を決定できます。合計で４回の比較です。
[1] → [2] → [3] → [4] → [5]

不正解の挿入順

では、先に[3]を挿入し、次に[1]を挿入すると、比較回数は何回になるでしょうか？
答えは５回です。不思議ですね。
なぜそうなるのか、また確認してみましょう。

[2] → [4] → [5]
             ↑
            [3]  [1]
//整列した要素[2][4]に、新しい要素[3]を挿入すると、
//バイナリインサートでは最初に[4]と比較、次に[2]と比較して、
//計２回の比較で挿入場所を決定できます。([5]は先ほどと同じ理由で比較対象から省略)

[2] → [3] → [4] → [5]
                   
                      [1]
//整列した要素[2][3][4][5]に、新しい要素[1]を挿入します。
//すると、バイナリインサートでは最初に[4]と比較、次に[3]と比較、次に[2]と比較して、
//計3回の比較で挿入場所を決定できます。合計で5回の比較です。
[1] → [2] → [3] → [4] → [5]

不正解の挿入順では、２つ目の要素[1]を挿入する時に、バイナリインサートの効率が下がっている（３回に増えてしまった）ことがわかります。
このように、効率の低下を招かないために、新しい要素の挿入順番は厳に定められています。

Partition the uninserted elements yi into groups with contiguous indexes. There are two elements y3 and y4 in the first group, and the sums of sizes of every two adjacent groups form a sequence of powers of two. Thus, the sizes of groups are: 2, 2, 6, 10, 22, 42, ...

要素が21個の時

では最後に、21個の数値を整列するために、マージインサートソートがどのように比較と並べ替えをするのか、考えてみてください！

以下の画像が、助けになることを祈ります。

ここまでで、ペアを作成して、ペア内でソートして、大きい値でペアを作成して、、の繰り返しは終了。

ここまでで、ペア要素の挿入、のサイズ２の状態が終了。

これで、ソートが完了しました。