รายละเอียดภายในของ std::sort() ใน C++

คำอธิบาย

std::sort ใช้ Introsort (Introspective Sort) เป็น hybrid algorithm:

• เริ่มด้วย Quick Sort (เฉลี่ย O(n log n))
• ถ้าความลึก recursion เกิน 2 * log2(n) → สลับเป็น Heap Sort (worst-case O(n log n))
• ขนาดเล็ก (มัก < 16) → ใช้ Insertion Sort

ไม่เสถียร (unstable) แต่เร็วและรับประกัน O(n log n) worst-case

ตัวอย่างการใช้งาน

#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 << "Sorted array: ";
    for(int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    
    // เรียงมากไปน้อย
    sort(arr, arr + n, greater<int>());
    cout << "Descending: ";
    for(int i = 0; i < n; i++) cout << arr[i] << " ";
    
    return 0;
}

เอาต์พุต

Sorted array: 0 1 2 3 4 5 6 7 8 9
Descending: 9 8 7 6 5 4 3 2 1 0