ヒープソート

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

ヒープ構造を利用したソートアルゴリズム。データからヒープを構築し、最大（最小）要素を繰り返し取り出して整列する。計算量は常にO(n log n)で追加メモリがO(1)だが、キャッシュ効率がクイックソートより劣る。

データからヒープ（親が子以上の値を持つ完全2分木）を作り、根にある最大値を取り出してヒープを作り直す操作を繰り返して整列するアルゴリズム。最悪でも計算量はO(n log n)で、作業用の領域もほとんど要らない。

それぞれ整列済みの2つの列を、先頭どうしを比較して小さい方を取り出すことを繰り返し、1つの整列済みの列にまとめるアルゴリズム。マージともいい、要素数がm、nのときO(m＋n)で処理できる。マージソートの統合の段階や、キーの順に並んだ複数の順編成ファイル（マスタファイルとトランザクションファイルなど）をまとめる処理に使われる。

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

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

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

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

基準値（ピボット）を選び、それより小さい要素と大きい要素のグループに分割する処理を、各グループに再帰的に繰り返す分割統治の整列のアルゴリズム。平均の計算量はO(n log n)で実用上最も速い部類だが、ピボットの選び方が悪いと分割が偏り最悪O(n²)になる。安定な整列ではない。