PmergeMe::mergeInsertSort 関数解説ドキュメントこのドキュメントは、PmergeMeクラスの中核をなすmergeInsertSort関数について、そのアルゴリズムのステップと、std::vector版とstd::deque版でコードがほぼ同一である理由を解説します。1. 関数の目的と設計この関数は、**Ford-Johnsonアルゴリズム（マージ挿入ソート）**を実装しています。std::vectorとstd::dequeの2つのバージョンが用意されていますが、これは課題の要件である「コンテナごとの性能比較」を行うためです。重要な点: 両関数で使われているアルゴリズムのロジックは全く同じです。違いは、操作対象となるコンテナの型（std::vectorかstd::dequeか）だけです。これにより、純粋にコンテナの特性がパフォーマンスに与える影響を測定できます。2. アルゴリズムのステップ・バイ・ステップ解説アルゴリズムは、コメントに示されている通り、大きく4つのステップで構成されています。ステップ1：ペアの作成とペア内ソートstd::vector<std::pair<int, int> > pairs; int straggler = -1; // ... if (hasStraggler) { straggler = vec.back(); vec.pop_back(); }

for (size_t i = 0; i < vec.size(); i += 2) { if (vec[i] < vec[i + 1]) { pairs.push_back(std::make_pair(vec[i + 1], vec[i])); } else { pairs.push_back(std::make_pair(vec[i], vec[i + 1])); } } 目的: 比較回数を減らすための下準備を行います。処理内容:入力された数列を2つずつのペアに分割します。要素数が奇数の場合、最後の1つは「はぐれ要素 (straggler)」として別途保持します。各ペアの内部で一度だけ比較を行い、常に [大きい方の数, 小さい方の数] の順序になるようにstd::pairとして格納します。ステップ2：メインチェーンの再帰的ソートstd::vector<int> mainChain; for (size_t i = 0; i < pairs.size(); ++i) { mainChain.push_back(pairs[i].first); } mergeInsertSort(mainChain); 目的: ソート済みの「背骨」となるシーケンスを効率的に作成します。処理内容:すべてのペアの**「大きい方の数」だけ**を集めて、メインチェーンと呼ばれる新しいシーケンスを作ります。このメインチェーンに対して、mergeInsertSort関数を再帰的に呼び出し、完全にソートします。ステップ3：最適化された挿入// ... 最初の要素を挿入 ... mainChain.insert(mainChain.begin(), pairs[i].second);

// ... ヤコブスタール数を利用したループ ... for (size_t k = 2;; ++k) { // ... std::vector<int>::iterator it = std::lower_bound(...); mainChain.insert(it, valueToInsert); } 目的: ペアの「小さい方の数」（保留要素）を、最小限の比較回数でメインチェーンに挿入します。処理内容:まず、ソート済みメインチェーンの先頭要素に対応する「小さい方の数」を、メインチェーンの先頭に挿入します。これは比較なしで安全に行えます。残りの「小さい方の数」を、ヤコブスタール数から導き出される特殊な順番で挿入していきます。この順番は、二分探索 (std::lower_bound) を行う対象範囲が常に可能な限り小さくなるように最適化されています。std::lower_boundで最適な挿入位置を見つけ、insertで要素を挿入します。ステップ4：はぐれ要素の挿入と最終化if (hasStraggler) { std::vector<int>::iterator it = std::lower_bound(...); mainChain.insert(it, straggler); } vec = mainChain; 目的: 残った要素をすべて統合し、ソートを完了します。処理内容:ステップ1で保持しておいた「はぐれ要素」があれば、それを最後に二分探索で挿入します。完成したソート済みシーケンス (mainChain) を、元のコンテナ (vec または deq) にコピーして、処理を完了します。3. vector版とdeque版の違いコード上はほぼ同じですが、ステップ3のinsert操作において、内部的なパフォーマンスが異なります。std::vector: insertのたびに、後続の要素をメモリ上で一つずつずらす必要があり、これが高コストになる可能性があります。std::deque: insertはvectorほど高コストではありませんが、std::lower_bound（二分探索）の前提となるランダムアクセスが、vectorよりわずかに遅くなります。この性能差を実測することが、この課題の重要な目的です。