What sorting algorithm is used in GCC?

Question

From cplusplus.com std::sort , complexity is defined:

Complexity

Approximately N * logN comparisons on average (where N is the last-first). In the worst case, up to N2, depending on the specific sorting algorithm used in the implementation of the library.

I have some run-time restrictions for my applications. So I need to know if I should implement my own sorting algorithm or if it will be a waste of time. They are compiled using gcc, so I need to know which sorting algorithm gcc uses.

Answer 1

GCC uses the Mussers introsort variant. This ensures the worst-case O ( n log n ) runtime:

It starts with quicksort and switches to heapsort when the recursion depth exceeds a level based on ... the number of elements sorted.

An implementation can be found in stl_algo.h header in the __introsort_loop function.