ソートアルゴリズム

ソートアルゴリズムとは

ソートアルゴリズムは、データを昇順・降順に並べ替えるアルゴリズムの総称である。ES2019 以降の JavaScript の言語仕様が Array.prototype.sort() に要求しているのは「同じ値の要素の相対順序が保たれる」(安定である) ことだけで、どのアルゴリズムを使うかは処理系に委ねられている。Chrome と Node.js の V8 は 2018 年の V8 7.0 / Chrome 70 で従来のクイックソート実装を置き換え、TimSort (連続した昇順・降順の並びを見つけて併合する、マージソートと挿入ソートのハイブリッド) を採用した。

主要なアルゴリズム

選ぶときに見るのは、比較回数の桁 (平均と最悪) と、同じ値の要素が入力順を保つかどうかの 2 点である。最悪計算量は入力の並びが最も不利なときの上限であり、平均と桁が違うアルゴリズムは「どんな入力で遅くなるか」まで押さえておく必要がある。

アルゴリズム	平均	最悪	同じ値の並び順	特徴
バブルソート	O(n²)	O(n²)	隣どうしの交換だけで動くため入れ替わらない	教育用、実用には遅い
挿入ソート	O(n²)	O(n²)	同じ値の後ろへ挿し込むため保たれる	小さい配列に高速
マージソート	O(n log n)	O(n log n)	併合時に左側を先に取るため保たれる	追加メモリを O(n) 使う
クイックソート	O(n log n)	O(n²)	離れた要素を交換するため崩れる	分割が偏らなければ高速、インプレース
TimSort	O(n log n)	O(n log n)	挿入ソートと併合を組み合わせるため保たれる	V8 と CPython が採用
ヒープソート	O(n log n)	O(n log n)	木の根と末尾を入れ替えるため崩れる	インプレース、キャッシュ効率が低い

表に出ていない最良ケースの差も実務では効く。挿入ソートとバブルソートは整列済みの入力なら 1 巡で終わるため O(n) になり、TimSort も既にある昇順の並びをそのまま使うので n-1 回の比較で済む。マージソートとヒープソートは入力の並びによらず比較回数がほとんど変わらない。クイックソートの最悪 O(n²) は分割が毎回極端に偏ったときに現れるもので、V8 が以前使っていた実装では先頭・末尾・中間の中央値をピボットに選ぶことでこれを避けていた。

TypeScript での使用

既定の sort() は要素を文字列に変換してから比較するため、数値配列では意図しない順序になる。比較関数を渡すのが基本である。

// 数値のソート (デフォルトは文字列比較なので注意)
[10, 2, 30].sort(); // [10, 2, 30] ❌ "10" < "2" < "30" の文字列比較
[10, 2, 30].sort((a, b) => a - b); // [2, 10, 30] ✅

// オブジェクトのソート
users.sort((a, b) => a.age - b.age); // 年齢の昇順
users.sort((a, b) => a.name.localeCompare(b.name)); // 名前の辞書順

// 安定ソート (ES2019 で保証)
// 同じキーの要素の相対順序が保持される

安定ソート vs 不安定ソート

同じキーを持つ要素の順序が結果の意味を左右する場面では、安定かどうかが正しさそのものを決める。

入力: [{name: "Alice", age: 30}, {name: "Bob", age: 30}, {name: "Carol", age: 25}]

安定ソート (age でソート):
  Carol(25), Alice(30), Bob(30)  ← Alice と Bob の順序が保持

不安定ソート:
  Carol(25), Bob(30), Alice(30)  ← Alice と Bob の順序が変わる可能性

この性質を使うと、先に副キーで並べ替え、次に主キーで並べ替えるだけで多段の並び替えが書ける。不安定なソートではこの二段重ねが崩れるため、比較関数の中で副キーまで比較しなければならない。Array.prototype.sort() は ES2019 で安定と規定されたので、この書き方を処理系に依存せず使える。

計算量の直感

同じ 100 万件でも、計算量の桁が 1 つ違うと比較回数は桁違いになる。

計算量	100 万件の比較回数
O(n²)	1 兆回
O(n log n)	約 2,000 万回
O(n)	100 万回

1 兆回は約 2,000 万回の 5 万倍にあたる。実時間はマシンと比較関数の重さで変わるので秒数では語れないが、O(n log n) が体感で終わる規模でも O(n²) は待たされる処理になる、という桁の差として覚えておけばよい。

比較ソートに下限がある理由

n 個の要素の並び方は n! 通りある。1 回の比較で分かるのは「どちらが大きいか」の 2 通りだけなので、n! 通りを最後の 1 つに絞り込むには最悪の場合 log2(n!) 回の比較が要る。この log2(n!) が n log n に比例する量であり、比較だけを頼りにするソートは最悪計算量を O(n log n) より小さくできない。マージソート・ヒープソート・TimSort の最悪が揃って O(n log n) なのは、この下限に届いているからである。

下限が縛るのは最悪ケースだけで、整列済みのような当たりの並びは縛られない。TimSort が既に昇順の入力を n-1 回の比較で片付けられるのはそのためである。桁数が決まった整数やキーの範囲が分かっている場合は、比較以外の情報 (何桁目が何か・どの範囲に入るか) を使う基数ソートやバケットソートで O(n) 側へ抜けられる。

DynamoDB でのソート

DynamoDB はソートキー (SK) でアイテムを自動的にソートする。クエリ結果は SK の昇順で返され、ScanIndexForward: false で降順にできる。

実務での選択

並べ替えたい配列がメモリにあるなら、処理系の sort() をそのまま使えばよい。主要な処理系の実装は十分に最適化されており、自前実装が上回ることはまずない。効くのはアルゴリズムの選び直しより手前の設計で、比較関数が重いならキーを先に計算して持たせる、データベースから取るなら並べ替えた状態で受け取る (DynamoDB のソートキーや SQL の ORDER BY)、上位数件だけ必要なら全体を並べ替えずその分だけ取り出す、といった判断のほうが差になる。

さらに掘り下げるなら関連書籍が参考になる。