Sorting Algorithm

目的

順序のないデータを整列させる。検索、重複排除、表示の基盤である。

メカニズム

比較ソートには O(n log n) の下界がある。クイックソートは平均 O(n log n)、最悪 O(n²)、インプレースである。マージソートは O(n log n) で安定であるが O(n) の領域が必要である。ヒープソートは O(n log n) インプレースである。カウントソートと基数ソートは非比較型で O(n) を達成できる。安定ソートは等しい要素の相対順序を保つ。

ユースケース

• データベースの ORDER BY
• 検索のための前処理
• ランキングとリーダーボード
• ソートして隣接比較で重複排除

例

• 入力

  [3,1,4,1,5] → quicksort

  Output

  [1,1,3,4,5]

  O(n log n) average

よくあるエラー

Quicksort recursion overhead is high for small arrays

Use insertion sort for small arrays (a quicksort optimization)