內省排序

內省排序又稱Introsort，是一個相當偏門的排序算法，是由David Musser在1997年設計出來的。屬於比較排序算法的一種。
內省排序的實現過程是這樣的，首先由快速排序開始，當遞歸深度超過一定程度時，轉換為堆排序。所以內省排序既能在常規數據集上實現快速排序的高性能，又能在最壞情況下仍保持 O（N log N） 的時間複雜度。
在快速排序算法中，一個關鍵操作就是選擇基準點（Pivot）：元素將被此基準點分開成兩部分。最簡單的基準點選擇算法是使用第一個或者最後一個元素，但這在排列已部分有序的序列上性能很糟。Niklaus Wirth為此設計了一個快速排序的變體，使用處於中間的元素來防止在某些特定序列上性能退化為O（N ²）的狀況。這個3基準中位數選擇算法從序列的第一，中間和最後一個元素取得中位數來作為基準，雖然這個算法在現實世界的數據上性能表現良好，但經過精心設計的序列仍能大幅降低此算法性能。這樣就有攻擊者精心設計序列傳送到網際網路伺服器以進行拒絕服務（DOS）攻擊的潛在可能性。
Musser研究指出，在為3基準中位數選擇算法精心設計的100,000個元素序列上，introsort的運行時間是快速排序的1 / 200。在Musser的算法中，最終較小範圍內數據的排序由Sedgewick提出的小數據排序算法完成。