Which 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 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.

Sarcocarp

can you use something better than a comparison sort? – Allcot

Only in very exceptional cases will you be able to get a faster program than what the carefully written STL gives. One of the ideas behind STL is precisely to use C++'s facilities to avoid costly function calls and do operations inline as much as possible. And if you get something faster, the cost will be enormous. Measure where the bottlenecks are before digging in to "optimize." – Pyrometallurgy

Answer 1

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.

Boeke

Thanks. Could i also know from which version of gcc is it used? – Sarcocarp

@Miro As far as I know, every version of GCC uses introsort, because the GCC STL implementation is based on the original, pre-standard implementation of SGI, which already used introsort. As far as I know, Musser himself wrote the first version of this code. – Boeke

std::__introsort_loop(__first, __last, std::__lg(__last - __first) * 2); std::__final_insertion_sort(__first, __last); – Allcot

Answer 2

As it was already said, the algorithm is called introsort, a combination between Insertionsort, Quicksort & Heapsort.

The Problem with quicksort is, that It has a very bad worst-case complexity of O(n²), but needs only O(log(n)) extra storage compared to mergesort with O(n).

As pseudocode, it would look like this:

input : unsorted list output : sorted list

def void sort( L ):
depthLimit = 2*floor(log(L))

introsort(L, depthLimit);

def void introsort(L , depthLimit):
n = |L|;
if n ≤ 16 then
    insertionSort(L);

else if depthLimit == 0 then
    heapsort(L);

else
    p = quicksort_partition(A);
    introsort(L[0:p-1], depthLimit - 1);
    introsort(L[p+1:n], depthLimit - 1);

The main idea here is to use quicksort when it is not reaching its worst case complexity, if It does, using heapsort instead until we got part lists of the length 16, and use Insertionsort after then.

The worst and avg complexity is O(n*log(n)) which is as good as mergesort, but does not come with the problem of the linear extra storage.

The sorting algorithm is not stable, that is the only compromise you have to make compared to mergesort-

Angadresma