深度introsort切換到堆積

Question

我想了解introsort並找到稀缺資源。我的理解是它使用快速排序，但當遞歸變深時切換到堆排序。這是因爲快速排序通常比堆排序快，除非通話深度變得很深。

我的問題是，如何計算切換到heapsort之前的深度？ Wikipedia有floor(log(length_of_data))x2但我看過其他的東西。什麼是推理？我正確的算法想要堅持快速排序，直到它需要切換到堆排序的內存原因？

Answer 1

我已經看到範圍從〜1.5 * log2（n）到〜2.0 * log2（n）的深度限制。這是爲了避免O（n^2）的最壞情況時間複雜性，而不是出於空間原因。

通過使用循環和遞歸的組合，僅對每個分區的較小「一半」使用遞歸，然後循環回來拆分較大的分區並繼續，從而將空間複雜度限制爲O（log2（n））該過程。循環返回也減少深度計數器，因爲它被用來替換否則會是另一個遞歸級別。