C++のstd::sort()の内部動作を徹底解説

本記事では、C++における std::sort() 関数の内部動作について詳しく解説します。

std::sort() は、要素同士を比較しながら配列やコンテナを昇順にソートするための標準ライブラリ関数です。一見シンプルな関数に見えますが、その内部では「イントロソート（IntroSort）」と呼ばれる高度なアルゴリズムが採用されています。

イントロソート（IntroSort）とは

イントロソートは、クイックソート、ヒープソート、挿入ソートの3つのアルゴリズムを組み合わせたハイブリッド型のソート手法です。以下のような仕組みで動作します。

• まずクイックソートでソートを開始し、高速な平均性能を活かします。
• 再帰の深さが一定の閾値を超えると、最悪計算量 O(n log n) を保証するヒープソートに切り替えます。
• 要素数が少ない区間では、キャッシュ効率に優れた挿入ソートで仕上げを行います。

この組み合わせにより、std::sort() は平均・最悪ケースともに O(n log n) の時間計算量を実現しています。

使用例

それでは、実際のコード例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int arr[] = {1, 5, 8, 9, 6, 7, 3, 4, 2, 0};
    int n = sizeof(arr) / sizeof(arr[0]);

    sort(arr, arr + n);

    cout << "\nデフォルトのsort()でソートした結果 : \n";
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";

    return 0;
}

出力結果

デフォルトのsort()でソートした結果 :
0 1 2 3 4 5 6 7 8 9

補足：カスタム比較関数の利用

std::sort() は第3引数に比較関数（またはラムダ式）を渡すことで、降順ソートなど独自の並び替え基準を指定することも可能です。

// 降順でソートする例
sort(arr, arr + n, greater<int>());

このように std::sort() は柔軟性が高く、パフォーマンスにも優れているため、C++でのソート処理において第一選択となる関数です。