マージソート

データを半分に分割して再帰的に整列し、整列済みの部分列を統合（マージ）するアルゴリズム。計算量は常にO(n log n)で安定しており、安定ソート（同値要素の順序を保持）。外部ソートにも適用可能だが、O(n)の追加メモリが必要。

列を半分ずつに分割することを要素が1つになるまで繰り返し、整列済みの列どうしを併合（マージ）しながら全体を整列する分割統治のアルゴリズム。計算量はデータの並びによらずO(n log n)で、安定な整列である。併合のための作業領域が必要だが、順次アクセスで処理できるので、主記憶に入らない大量データの外部整列にも使われる。

データを半分ずつに分割していき、整列済みの小さな列どうしを併合（マージ）することを繰り返して整列するアルゴリズム。最悪でも計算量はO(n log n)で安定した整列ができるが、作業用の記憶領域が必要になる。

隣接する要素を比較して交換を繰り返すことでデータを整列するアルゴリズム。平均・最悪計算量ともにO(n²)で効率は良くないが、アルゴリズムが単純で理解しやすい。安定ソート。

未整列部分から最小値（または最大値）を見つけて先頭に移動する操作を繰り返す整列アルゴリズム。計算量はO(n²)で、交換回数が少ないがデータ比較は多い。不安定ソート。

未整列部分の先頭要素を整列済み部分の適切な位置に挿入する操作を繰り返す整列アルゴリズム。平均・最悪計算量はO(n²)だが、ほぼ整列済みのデータに対してはO(n)で高速。安定ソート。

基準値（ピボット）を選び、それより小さい値と大きい値に分割する操作を再帰的に繰り返す整列アルゴリズム。平均計算量はO(n log n)で高速だが、最悪の場合O(n²)になる。不安定ソート。

ヒープ構造を利用した整列アルゴリズム。データをヒープに構築し、最大値（最小値）を取り出す操作を繰り返す。最悪計算量がO(n log n)で安定しており、追加メモリが不要。不安定ソート。

一定間隔だけ離れた要素どうしを挿入ソートで整列し、間隔を徐々に狭めながら繰り返す整列法。最後は間隔1の挿入ソートになるが、大きな移動を先に済ませているため単純な挿入ソートより高速になる。