多重キーソートとは？
多重キーソート（Multi-key Sort）は、1つの基準で順序が決まらないとき次の基準を使うソートです。座標(x, y)のように値が2つあり、1つの数として比較できないデータに不可欠です。
ルールは単純です。「まずxで比較し、xが同じときだけyで比較する」。xを第1キー、yを第2キーと呼びます。
なぜ重要か？
現実のソートはほとんどが多重キーです。
- •座標ソート: x順、同じならy順（計算幾何・ゲームマップ）
- •氏名ソート: 姓で、同じなら名で
- •ランキング: スコア降順、同じなら時間昇順
コーディングテストでも「x昇順、同じならy昇順で出力せよ」という条件が頻出します。
比較関数が核心
多重キーソートのすべては比較関数に詰まっています。
compare(a, b):
if a.x != b.x: return a.x - b.x # 第1キー: x
return a.y - b.y # 第2キー: y（xが同じときのみ）xが異なればその場で決まり、xが同じ場合だけyへ進みます。 この「同点のときだけ次のキー」という流れが多重キーの本質です。
動作原理（例）
points = [(3,1), (1,4), (3,0), (2,2)] をソートしてみましょう。
ステップ1. xで並べる → (1,4) / (2,2) / (3,0)・(3,1)
ステップ2. xが3で同じ(3,0)と(3,1)はyで決定 → (3,0)が先
結果. [(1,4), (2,2), (3,0), (3,1)]
ポイントは(3,0)が(3,1)より前に来ること。第2キーyがなければ、この2つの順序は保証されません。
時間計算量
| 方式 | 時間計算量 |
|---|---|
| バブルソートでデモ | O(n²) |
| 実務の比較ソート(comparator) | O(n log n) |
比較関数自体はO(1)です。キーが何個でも定数時間なので、全体の計算量は使うソートアルゴリズムが決めます。学習用の可視化は比較を一回ずつ見せるためにバブルソートを使いますが、実務ではソート関数に比較子を渡してO(n log n)で処理します。
よくあるミス
- •第2キーの抜け: xだけ比較すると、xが同じ要素の順序がバラバラになります。
- •同点条件の勘違い: 「xが異なるときもyを見る」と書くと結果が誤ります。yはxが同じときだけ見ます。
- •符号の混同: 昇順は
a - b、降順はb - a。キーごとに方向が違うことがあるので注意しましょう。
AlgoNoteで直接確認しましょう
xを比較するステップと、同点のときyへ進むステップがどう分かれるか、AlgoNoteで一段階ずつ確認できます。