ENGINEER_SPEC: 応用ソート
新人エンジニアが実務でソートを選ぶ基準は「時間」「メモリ」「安定性」の3点です。
1. クイックソート
ピボットを基準にデータを分割します。平均速度は最速ですが、データの並びによっては最悪 O(n^2) に落ちるリスクがあります。非安定ソートです。
2. マージソート
分割して整列してから合体させます。常に安定した速度を発揮し、同じ値の順序が崩れない安定ソートですが、作業用に O(n)
の追加メモリが必要です。
3. シェルソート
挿入ソートの改良版です。一定間隔（ギャップ）でソートを繰り返し、徐々に間隔を詰めます。小〜中規模データに強く、メモリ消費が極めて少ないのが特徴です。
4. ヒープソート
木構造（ヒープ）を構築し、最大値を取り出し続けます。メモリ効率が良く、最悪ケースでも速度が落ちません。組み込み等の制約が厳しい環境で重宝されます。