この記事のポイント

  • stable_sortとsortの違いをレビューアー視点で整理
  • 安定ソートの要否がAPI契約にどう現れるかを理解
  • 安易な選定を防ぐ設計レビュー技術を学べる

そもそもソート安定性とは

安定ソート (Stable Sort) とは、ソートキーが等しい要素同士の順序を元の順序通りに保持するソートのことです。
逆に不安定ソート (Unstable Sort) はキーが等しい要素間の順序が崩れる可能性があります。

特性 安定ソート 不安定ソート
同一キー順序保持 保持する 崩れる可能性
代表アルゴリズム stable_sort, insertion_sort sort, quicksort, heapsort
計算量傾向 高め 低め（最適化可能）
API例 std::stable_sort std::sort
  • stable_sort ≠ sortが常に優れている ではない
  • 「保持したい順序情報」があるか否かが選定基準となる

なぜこれをレビューするのか

レビューアー視点

ソート安定性の選定は設計意図がそのまま現れます。

  • 第二順位ソート要否
    → 複数条件ソートの途中段階順序が壊れて困らないか

  • ソートの契約明記
    → 呼び出し側が安定性を前提にしていないか

  • アルゴリズム特性負荷
    → O(N log N) vs O(N log² N)コストを理解しているか

  • デバッグ負荷意識
    → 安定性崩壊が副作用を誘発していないか

開発者視点

  • 常にstd::sortを使う癖
  • 安定ソートの必要性自体を知らない
  • 安定性を保証せず副作用的に依存
  • 計算量コストを把握していない

レビューアーはこうした設計責任の意識漏れを補います。

良い実装例

ユースケース：APIリクエストログを時刻優先、同時刻ならrequestId順に安定ソート

良い実装例：安定ソート利用 
#include <vector>
#include <string>
#include <algorithm>
#include <cstdint>

struct ApiRequestLog {
    std::string requestId;
    int64_t requestedAt;
};

// 時刻優先、requestId次順位
void sortLogs(std::vector<ApiRequestLog>& logs) {
    std::stable_sort(logs.begin(), logs.end(), [](const ApiRequestLog& a, const ApiRequestLog& b) {
        return a.requestedAt < b.requestedAt;
    });
}
  • 元データ生成順序に依存情報あり
  • 二次的情報保持にstable_sortが必要
  • 事前にrequestId順ソート済みでも破壊されない

レビュー観点

  • 安定性が設計契約上必要か
  • 呼び出し側が順序保証を期待していないか
  • 計算量コスト許容が示されているか
  • 単純に「なんとなくsortを選んでいないか」
  • 不安定性の副作用が潜在バグ源になっていないか

良くない実装例: ケース1

以下は安定性要件を無視してsortを使ってしまった例です。

sort誤用例：安定性崩壊 
void sortLogs(std::vector<ApiRequestLog>& logs) {
    std::sort(logs.begin(), logs.end(), [](const ApiRequestLog& a, const ApiRequestLog& b) {
        return a.requestedAt < b.requestedAt;
    });
}

@Reviewer
安定ソートが必要な設計です。std::sortでは順序崩壊の副作用が発生します。std::stable_sortへ変更してください。

問題点

  • 同時刻データの生成順序が破壊される
  • 並列ソートや実装依存で出力順序不定
  • 障害再現困難バグが生まれやすい

改善例

修正例：stable_sortへ変更 
void sortLogs(std::vector<ApiRequestLog>& logs) {
    std::stable_sort(logs.begin(), logs.end(), [](const ApiRequestLog& a, const ApiRequestLog& b) {
        return a.requestedAt < b.requestedAt;
    });
}

良くない実装例: ケース2

次は安定性が不要なのに過剰にstable_sortを使っている例です。

過剰安定性例 
void sortLogsByRequestId(std::vector<ApiRequestLog>& logs) {
    std::stable_sort(logs.begin(), logs.end(), [](const ApiRequestLog& a, const ApiRequestLog& b) {
        return a.requestId < b.requestId;
    });
}

@Reviewer
安定性は必要ありません。比較コスト削減のためstd::sortで十分です。

問題点

  • 単一キーによる一次元完全ソートでは安定性が無意味
  • stable_sortは不要な性能コスト負担になる

改善例

修正例：不要な安定性排除 
void sortLogsByRequestId(std::vector<ApiRequestLog>& logs) {
    std::sort(logs.begin(), logs.end(), [](const ApiRequestLog& a, const ApiRequestLog& b) {
        return a.requestId < b.requestId;
    });
}
  • 安定性は「意味ある二次順位」が存在する時のみ必要
  • 無条件にstable_sortを使う癖は避ける

PlantUMLで安定性適用責務整理

UML Diagram

観点チェックリスト

まとめ

ソート安定性は「要るか要らないか」ではなく、契約責任の所在を誰が持つのか という設計論点です。
レビューアーは安定性の要否を読み違えることなく、

  • API利用契約
  • 二次順位存在有無
  • 実行性能責任

これらを冷静に判断する役割を担います。
レビュー現場では「sort使ったから安心」といった発想を早期に訂正していきましょう。