Which sorting algorithm is used in GCC?
c++, gcc, time-complexity
Solution
GCC uses a variation of Musser’s introsort. This guarantees a worst-case running time of O(n log n):
It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on … the number of elements being sorted.
The implementation can be found in the `stl_algo.h` header in the `__introsort_loop` function.
Problem
From cplusplus.com `std::sort` complexity is defined: Complexity Approximately N*logN comparisons on average (where N is last-first). In the worst case, up to N2, depending on specific sorting algorithm used by library implementation. I have some limitations at running time for my apps. So i need to know if should i implement my own sorting algorithm or it would be only waste of time. They are compiled with gcc, so i need to know which sorting algorithm gcc uses.