値が同じでもレコードは同じではない
安定ソートは、比較に使うキーが等しいレコードについて、入力での前後関係を保つ整列です。キー2のAとC、キー1のBとDを用意し、[A2,B1,C2,D1]の順で渡します。キーだけを[1,1,2,2]と表示しても、安定かどうかは分かりません。そこで名前を付けたレコードのまま出力し、BがDより先、AがCより先であることを調べます。これは同じレコードが毎回同じ位置に来るという意味ではなく、同値キーのグループ内で元の順序が残るという性質です。
比較キーを明示して実行する
Pythonのsortedへkey関数を渡し、整数のキーだけで比較します。ラベルを含むタプル全体を直接整列すると、同じ整数の中でラベルが次の比較要素になり、調べたい「キーが等しい」の定義が変わります。元の配列を変更しないsortedと、その場で変更するlist.sortの違いも分けて確認します。下のassertは出力順だけでなく、入力配列が保持されたことも確かめます。目的に応じたAPIを選び、整列結果と元データのどちらを後続処理へ渡すかを曖昧にしないようにします。
records = [("A", 2), ("B", 1), ("C", 2), ("D", 1)]
ordered = sorted(records, key=lambda row: row[1])
assert [r[0] for r in ordered] == ["B", "D", "A", "C"]
assert records == [("A", 2), ("B", 1), ("C", 2), ("D", 1)]
# A multi-pass stable sort: secondary key first, primary key last.
rows = [("x", 2), ("y", 1), ("x", 1), ("y", 2)]
by_secondary = sorted(rows, key=lambda row: row[1])
by_both = sorted(by_secondary, key=lambda row: row[0])
assert by_both == sorted(rows, key=lambda row: (row[0], row[1]))
print(ordered, by_both)
二つのキーを順番に扱う
主キーを文字列、第二キーを整数とするレコードも試します。まず第二キーで安定に整列し、その結果を主キーで安定に整列します。後の処理は主キーの同値グループ内の順序を保つため、第二キーの順序が残ります。これを主キーと第二キーの組による一回の整列結果と比較します。先に主キー、最後に第二キーという逆の順序では、最後のキーが最優先になり、一般には望む結果と一致しません。多段の整列を使う場合は、低い優先順位から処理するという約束を例で確かめます。
入力順そのものが揺れる場合
安定ソートは、与えられた入力順を保存する性質です。入力が順序の保証されない外部取得や並列収集から来るなら、実行ごとに入力の前後関係が変わる場合があります。安定ソートを使うだけで、その揺れが自動的に消えるわけではありません。毎回同じ一覧が必要なら、日時と一意なIDなど、同値を解消する明示的なキーを仕様に含めます。順位を決める規則を増やすことと、既存の同値レコードの順序を保つことは別の判断です。表示の再現性が必要なのか、元の優先順位を尊重したいのかを先に決めます。
文字列・欠損値・比較規則を分ける
この例では整数と簡単な英字だけを使います。大文字小文字を同じに扱う、言語別の照合順を使う、欠損値を先頭か末尾へ置くといった要件は、安定性とは別に定義します。文字列を小文字へ変換するkey関数を使えば、比較上は同じでも表示文字列が異なるレコードが生まれます。そこでも安定性は変換後のキーに対して働きます。互いに比較できない型を無条件に混ぜたり、実行中に値が変わる比較規則を使ったりしないようにし、どの意味で整列したのかをテストへ書きます。
順序の正しさと速さを別々に測る
まず同値グループの順序と全体のキー順をassertで検査し、その後に必要なら速度を測ります。この小さな四件の例から大規模データの実行時間は推定できません。入力の既存の順序、キー計算の費用、レコードの参照方法にも影響されます。整列が安定であることだけから、補助領域が不要だと結論することもできません。ほかの言語やライブラリへ移す場合は、そのAPIが安定性を保証するかを公式の契約で確認し、同じラベル付きの例を使って差を確かめます。