併合のアルゴリズム

それぞれ整列済みの2つ以上のデータ列を、整列順を保ったまま1つの列にまとめるアルゴリズム。各列の先頭どうしを比べて小さい方を取り出すことを繰り返し、全体を1回たどるだけで併合できる。マージソートや、ファイルの突合せ処理で使われる。

複数のデータソースに分散する同一の対象（顧客や取引先など）のレコードを見つけて、1つにまとめる処理。項目の一致や類似度で同一とみなす候補を探すマッチング、統合するマージ、誤って統合したものを戻す分割、結果の確認・是正の手順で行い、マスターデータのゴールデンレコードを作る。

大きな問題を同じ種類の小さな部分問題に分割し、部分問題をそれぞれ（多くは再帰的に）解いて、その結果を統合して元の問題の解を得るアルゴリズムの設計方法。マージソート、クイックソート、2分探索、高速フーリエ変換が代表例である。半分ずつに分けて統合をO(n)で行える場合、全体はO(n log n)になることが多い。

整列済みのデータで、探索範囲の中央の値と目的の値を比較し、目的の値がある側の半分に範囲を絞ることを繰り返す探索の方法。1回の比較で範囲が半分になるので、データ数nに対する最大の比較回数は約log₂n回で、計算量はO(log n)である。データが整列している必要があり、追加・削除が多いデータでは整列を保つ費用がかかる。

隣り合う要素を比較して、順序が逆なら交換する操作を列の端から端まで繰り返し、大きい（または小さい）値を泡が浮かぶように端へ移していく整列のアルゴリズム。計算量は平均・最悪ともO(n²)と遅いが、仕組みが単純で、同じキーの要素の順序が保たれる安定な整列である。

未整列の部分から最小（または最大）の要素を選び、未整列の部分の先頭と交換することを繰り返す整列のアルゴリズム。比較の回数はデータの並びによらず約n²/2回で、計算量はO(n²)である。交換の回数はn－1回以下と少ないが、離れた要素を交換するので安定な整列ではない。

整列済みの部分に、未整列の部分の先頭の要素を適切な位置へ挿入することを繰り返す整列のアルゴリズム。計算量は平均・最悪でO(n²)だが、ほぼ整列済みのデータではO(n)に近く速い。安定な整列で、要素数の少ない区間の整列としてクイックソートなどと組み合わせて使われる。