Che magia usa `std :: sort` internamente che lo rende molto più veloce?

Question

Ho un'implementazione Quicksort banale che va sotto:

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); 
    } 
    } 
} 

test su un array di elementi 1000000 dura circa per sempre (6300 ms) prima volte di morire di ricorsione, mentre std::sort prende come 30 ms.

Sicuramente non mi aspetto che la mia pessima implementazione sia veloce quanto std::sort ma come può esserci una differenza così grande?

Capisco std::sort utilizza qualcosa di più complicato di un semplice quicksort (credo sia un introsortale) che impedisce di andare troppo lontano nel livello di ricorsione e roba del genere. Ma ancora, c'è qualcosa di ovvio che mi manca che potrebbe spiegare una differenza così grande?

Variare la dimensione dello scam mostra che il fattore di differenza non è costante, in realtà sembra crescere come n².

Answer 1

Verificare prima la selezione del perno migliore (comunemente, la mediana di 3 viene utilizzata) ed eliminare un ramo della ricorsione per risparmiare spazio nello stack.

La selezione pivot ha l'impatto maggiore sulle prestazioni algoritmiche complessive, poiché fa la differenza tra N * log (n) e N^2.

Answer 2

Supponendo che il codice sia corretto (quicksort può essere ingannevole) quindi suppongo che la grande differenza è che non si sta utilizzando un ordinamento più veloce quando il numero di elementi è piccolo. Ad esempio, è comune utilizzare l'ordinamento di selezione quando il numero di elementi da ordinare è inferiore a qualche numero piccolo.

Quel codice C++ 11 rinky-dink mi fa anche sospettare, anche se ammetto che non saprò nulla.