Sortowanie introspektywne (ang. introspective sort lub introsort) – odmiana sortowania hybrydowego, w której wyeliminowany został problem złożoności O(n2) występującej w najgorszym przypadku algorytmu sortowania szybkiego.
Sortowanie hybrydowe
Pomysł Sortowania hybrydowego opiera się na spostrzeżeniu, że ogromna liczba rekurencyjnych wywołań algorytmu sortowania szybkiego jest realizowana dla małych tablic. W przypadku małych tablic czynności organizacyjne dokonywane przez procedurę Partition, takie jak wyznaczenie mediany z trzech, przygotowanie wskaźników i sprawdzanie warunków na nie nakładanych, zajmują relatywnie dużo czasu w stosunku do rozmiaru samej tablicy. Poza tym, samo wywołanie rekurencyjne jest czasochłonne i zajmuje miejsce na stosie, a dla 5-elementowej tablicy mogą być potrzebne nawet 3 wywołania. Dlatego też w algorytmie sortowania hybrydowego przyjęto, że małe tablice będą sortowane jednym z elementarnych algorytmów sortowania, które chociaż mają kwadratową złożoność obliczeniową, dla zbiorów o niewielkim rozmiarze działają relatywnie szybko.