Introsort eller introspektiv sortering är en sorteringsalgoritm som föreslagits av David Musserår 1997. Den använder quicksort och växlar till heapsort när rekursionsdjupet överstiger någon förutbestämd nivå (som logaritmen för antalet sorterade element). Detta tillvägagångssätt kombinerar styrkorna hos båda metoderna med ett O ( n log n ) worst case och hastighet jämförbar med quicksort. Eftersom båda algoritmerna använder jämförelser, tillhör denna algoritm också den jämförelsebaserade sorteringsklassen .
Vid quicksort är en av de kritiska operationerna valet av ett stöd (det element med avseende på vilket arrayen är delad). Den enklaste algoritmen för att välja en grund - att ta det första eller sista elementet i en array som stöd är fylld av dåligt beteende på sorterad eller nästan sorterad data. Niklaus Wirth föreslog att man skulle använda mittelementet för att förhindra att detta fall försämras till O( n ²) på dåliga ingångar. Medianen för tre stödvalalgoritmer väljer mitten av de första, mitten och sista elementen i arrayen som stöd. Men även om den fungerar bra på de flesta ingångar, är det fortfarande möjligt att hitta ingångar som saktar ner denna sorteringsalgoritm mycket. Sådan data kan potentiellt användas av angripare. Till exempel kan angripare skicka en sådan array till en webbserver för att uppnå ett överbelastningsskydd .
Musser fann att på den sämsta datamängden för medianen av tre quicksort- algoritmen (en array av 100 000 element övervägdes), är introsort ungefär 200 gånger snabbare. Han bedömde också cacheeffekten i fallet med Robert Sedgwick- sorteringen , där små intervall sorteras i slutet av en enda insättningssorteringspass . Han fann att detta tillvägagångssätt kan fördubbla antalet cachemissar, men dess prestanda är mycket bättre när man använder en deque och bör överlåtas till mallbibliotek, delvis för att vinsterna inte är stora annars.
SGI :s implementering av C++ Standard Template Library ( stl_algo.h ) använder Mussers rekursionsdjupstyrningsmetod för instabil sortering , byter till heapsort , väljer ett fast element som median av tre och tillämpar slutligen Knuths insättningssorteringsalgoritm för sekvenser som innehåller mindre än 16 element.
| Sorteringsalgoritmer | |
|---|---|
| Teori | Komplexitet O notation Orderförhållande Sorteringstyper hållbar Inre Extern |
| Utbyta | |
| Val | |
| Insatser | |
| fusion | |
| Inga jämförelser | |
| hybrid | |
| Övrig | |
| opraktisk | |