この記事のポイント

  • stable_sortとsortの適用判断をレビューアー視点で整理
  • 順序保証責任とAPI契約責任の違いを読み解く技術を養う
  • 安定性設計が性能や保守性に及ぼす影響をレビューで評価

そもそもsortとstable_sortの違い

特性 sort stable_sort
安定性 保証しない（不安定ソート） 保証する（安定ソート）
計算量 O(N log N) O(N log² N) or O(N log N)（実装依存）
意図 最速で並べる 順序保持しつつ並べる
利用場面 単純キーソート 複合キーソート・段階的ソート
  • 安定ソート＝等値要素の元順序維持
  • 不安定ソート＝等値要素の順序破壊可能性あり

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

レビューアー視点

sort選択はAPI契約と設計意図が直結する責任領域。

  • 順序保証責任の所在整理
    → 呼出側が順序前提を置くか否か確認

  • 二次順位存在性の有無確認
    → sort前処理による段階ソート適用有無確認

  • パフォーマンス責任の妥当性確認
    → 安定性コストを許容できる設計か

  • デバッグ再現性責任
    → ソート結果順序が障害調査困難要因化しないか

開発者視点

  • sort一択思考
  • stable_sort存在意義理解不足
  • 安定性必要性の見極め不在
  • 複合キー設計意識薄弱

レビューアーはこれら「順序設計責任抜け落ち」を早期検出する役割を担う。

良い実装例

ユースケース：APIレスポンスをタイムスタンプ優先、同時刻ならrequestId順で安定ソート

良い実装例：安定性必要設計 
#include <vector>
#include <string>
#include <algorithm>
#include <cstdint>

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

void sortByRequestedAt(std::vector<ApiRequestLog>& logs) {
    std::stable_sort(logs.begin(), logs.end(),
        [](const ApiRequestLog& a, const ApiRequestLog& b) {
            return a.requestedAt < b.requestedAt;
        });
}
  • 事前にrequestId順ソート済前提設計でも破壊しない
  • 等値時順序保証が契約に含まれている

レビュー観点

  • 二次順位の順序保証が必要な設計か
  • 呼出側が順序保証を期待していないか
  • 安定性コストを性能設計で吸収できているか
  • デバッグ再現性が安定性依存で乱れていないか

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

以下は安定性必要場面でsortを用い誤動作誘発している例。

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

@Reviewer
等値時順序保証が設計要件です。stable_sortへ変更してください。

問題点

  • 同一requestedAt時のrequestId順序破壊
  • 並列ソート実装時に不安定順序が発生

改善例

修正例：安定ソート適用 
std::stable_sort(...);

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

次は安定性不要な単純キーソートでもstable_sortを安易適用している例。

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

@Reviewer
二次順位が無いため安定性不要です。sort使用で性能向上可能です。

問題点

  • 不必要な安定性コスト負担
  • 意図が設計上曖昧化

改善例

修正例：不要安定性排除 
std::sort(...);

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

次は複合キーソート設計を明文化せず一括比較に依存している例。

複合キー未整理例 
std::sort(logs.begin(), logs.end(),
    [](const ApiRequestLog& a, const ApiRequestLog& b) {
        return std::tie(a.requestedAt, a.requestId) < std::tie(b.requestedAt, b.requestId);
    });

@Reviewer
複合キーソートは段階安定ソート設計で整理可能です。意図明文化推奨です。

問題点

  • 一括比較は安定性設計を曖昧化
  • 二次順位設計意図が埋没

改善例

修正例：段階ソート構造整理 
std::sort(logs.begin(), logs.end(),
    [](const ApiRequestLog& a, const ApiRequestLog& b) {
        return a.requestId < b.requestId;
    });

std::stable_sort(logs.begin(), logs.end(),
    [](const ApiRequestLog& a, const ApiRequestLog& b) {
        return a.requestedAt < b.requestedAt;
    });
  • 段階的安定ソートで設計意図が明示化される

API契約と安定性責任整理

パターンA：順序保証責任をAPI契約に含める

void sortByTimestamp(std::vector<ApiRequestLog>& logs);
// → 二次順位順序維持が契約責任に含まれる

パターンB：順序保証を契約外にする

void sortForExport(std::vector<ApiRequestLog>& logs);
// → 結果順序は不定（性能最優先）

stable_sort適用判断整理表

条件 stable_sort要否
二次順位設計有 必要
検査順序で出力保証必要 必要
単一完全順序 不要
デバッグ再現性要求高 必要

sort/stable_sort設計対比表

項目 sort stable_sort
主用途 単一キー完全順序 複合キー分離設計
設計責任 性能重視 契約重視
順序保証 不定 保証
デバッグ再現性 低 高
コスト負荷 低 やや高

PlantUMLで設計責任整理

UML Diagram

観点チェックリスト

実務レビューFAQ

Q1. sortは安定性保証ゼロ？
→ その通り。順序は破壊される。二次順位あるならstable_sort必須。

Q2. 安定ソートは遅い？
→ 最近の実装ではO(N log N)高速化も多いが原理的負荷はやや高い。

Q3. sortで複合キー比較して良い？
→ 小規模なら容認。だが設計明文化上は段階安定ソートの方が良い。

Q4. デバッグ再現性に影響する？
→ 安定性有無で出力順序が障害再現容易性に直結するケースあり。

Q5. sort→stable_sort切替レビューは重要？
→ 非常に重要。設計契約読み取り力の訓練箇所。

まとめ

sortとstable_sortの使い分けはAPI契約設計力の核心項目である。
レビューアーは

  • 順序保証責任
  • 二次順位存在性
  • デバッグ再現性責任
  • 性能責任バランス

これらを仕様段階で読み取る力を養う必要がある。
レビューアーがsortとstable_sortを語れると設計レビュー精度が格段に上がる。