Ի՞նչ ալգորիթմ է իրականացվում C++-ի std::sort ֆունկցիայի ներսում։

C++ ստանդարտ գրադարանում std::sort ֆունկցիան իրականացվում է Introsort (մտածողային դասակարգում) ալգորիթմի միջոցով: Սա հիբրիդային ալգորիթմ է, որը համատեղում է.

• Արագ դասակարգում (Quicksort) մեծ մասամբ դեպքերում:
• Հավասարակշռված բուրգային դասակարգում (Heapsort)՝ երաշխավորելով ամենավատ դեպքի ժամանակը O(n log n), եթե ռեկուրսիայի խորությունը շատ մեծանա:
• Միջնորդային դասակարգում (Insertion sort) փոքր ենթամասիվների համար, ինչը բարձրացնում է արդյունավետությունը:

Introsort-ը սկսում է արագ դասակարգումից, բայց եթե ռեկուրսիայի խորությունը գերազանցում է որոշակի շեմը (սովորաբար կապված զանգվածի չափի լոգարիթմի հետ), այն անցնում է բուրգային դասակարգման՝ կատարողականի անկումը կանխելու համար:

Այսպիսով, այն ապահովում է միջին արդյունավետություն և երաշխավորված ժամանակ Worst-case-ում։