什么时候introsort从快速排序转换为堆排序？

Question

Introsort 从快速排序开始，当递归深度超过基于被排序元素数量的水平时，转而使用堆排序。那个数字是多少？有特定的范围或限制值吗？

- sachin irukula

Answer 1

Introsort算法从Quicksort切换到Heapsort的点由depth_limit决定:

depth_limit = 2 · ⎣log₂(l)⎦

其中l是要排序的序列长度，因此整个序列的l‍=‍n。每次递归调用时，depth_limit减少1。当depth_limit达到0时，它从Quicksort转换为Heapsort。

- Gumbo

---

按照你的逻辑，堆排序永远不会发生，因为深度限制永远不会被达到。 - this

@self。你为什么这样想？ - Gumbo

请阅读我的评论; 另一个例子：如果数组在每次递归时大致分成两半，则具有10000个成员的数组将具有深度限制（13 * 2），则在第14级别上，子数组将具有0个元素。 - this

将序列分成两半是最好的情况，最坏的情况是序列被分成(1,N-1)两部分。在这种情况下，深度限制会达到0。 - Gumbo

Answer 2

我刚试着阅读了维基百科文章的介绍（链接）。它说：

算法会计算递归深度。如果超过对数深度，算法会从快速排序切换到堆排序，以保持快速排序的最坏情况结果。

并且通过Musser的原始论文介绍了Introsort。

论文中提到，Introsort比Heapsort慢，因为在切换到堆排序之前要执行2*log(2,N)次计算。

我的理解是递归深度是2*log(2,N)

例如：对于要排序的300个元素，递归深度将是2*8=16。

- pyfunc

---

如果在一个有300个元素的数组上使用深度限制为16，那么在大约第10个深度级别时，子数组将会有0个元素。 - this