Jaką magię używa `std :: sort` wewnętrznie, co sprawia, że ​​jest o wiele szybsza?

Question

mam trywialne wdrożenie quicksort, że idzie przez:

template <typename IteratorType> 
void quicksort(IteratorType begin, IteratorType end) 
{ 
    if (begin != end) 
    { 
    const auto pivot = *(begin + distance(begin, end)/2); 
    const IteratorType sep = std::partition(begin, end, [pivot](typename IteratorType::value_type v){ return (v < pivot); }); 

    if (sep != begin) 
    { 
     quicksort(begin, sep); 
    } 

    if (sep != end) 
    { 
     quicksort(sep + 1, end); 
    } 
    } 
} 

testowanie go na 1000000 elementów tablicy odbywa się zawsze (6300 ms) przed czasem umierają z rekurencji, natomiast std::sort trwa jak 30 ms.

Z pewnością nie spodziewam się, że moja ponura implementacja będzie tak szybka jak std::sort, ale jak może istnieć tak ogromna różnica?

Rozumiem, że std::sort używa czegoś bardziej skomplikowanego niż prosty quicksort (uważam, że jest introsort), który zapobiega zbyt daleko na poziomie rekurencji i tym podobnym. Ale czy jest coś oczywistego, co może mi wyjaśnić tak wielką różnicę?

Zróżnicowanie wielkości arii pokazuje, że współczynnik różnicy nie jest stały, tak naprawdę rośnie on jak n².

Answer 1

Najpierw sprawdź lepszy wybór przestawny (zwykle używana jest mediana 3) i wyeliminuj jedną gałąź rekursji, aby zaoszczędzić miejsce na stosie.

Wybór pivot ma największy wpływ na ogólną wydajność algorytmiczną, ponieważ odróżnia N * log (n) od N^2.

Answer 2

Zakładając, że kod jest poprawny (quicksort może być trudny), to myślę, że duża różnica polega na tym, że nie używasz szybszego sortowania, gdy liczba elementów jest mała. Na przykład często stosuje się sortowanie selekcji, gdy liczba elementów do posortowania jest mniejsza niż niewielka liczba.

Ten podejrzany kod C++ 11 również mnie podejrzewa, chociaż przyznaję, że nic o tym nie wiem.