Jeśli tablica jest podzielona na podzbiory w taki sposób, jak opisano powyżej, to elementy każdego podzbioru będą porównywane tylko ze sobą.
Sortowanie introspektywne
Głównym założeniem algorytmu Sortowania introspektywnego jest obsługa najgorszego przypadku algorytmu sortowania szybkiego tak, aby zapewnić logarytmiczno-liniową złożoność obliczeniową. Przypomnijmy, że w najgorszym przypadku podziały wykonywane przez procedurę Partition były zdegenerowane i algorytm sortowania szybkiego wykonywał O(n2) porównań.
Rozwiązaniem problemu złożoności obliczeniowej O(n2) w najgorszym przypadku jest badanie głębokości rekurencji. W procedurze głównej sortowania introspektywnego – Hybrid Introspective Sort – tworzona jest stała M o wartości 2∙log2n, która określa maksymalną dozwoloną głębokość wywołań rekurencyjnych. Następnie wywoływana jest procedura Intro Sort. Procedura Intro Sort przyjmuje jako dodatkowy parametr wartość M, która określa maksymalną dozwoloną głębokość wywołań rekurencyjnych z poziomu, na którym obecnie się znajdujemy. Jeżeli wartość parametru M wynosi 0, wywołania rekurencyjne są kończone i dla podproblemu, którym obecnie się zajmujemy, wywoływana jest procedura sortowania przez kopcowanie, które jest traktowane jako sortowanie pomocnicze.