c++ - STL std::sort() 使用 Introsort，但它是如何工作的？

Question

我并没有真正了解 Introsort 算法。如您所见，我添加了它的伪代码。最大深度是什么意思？

⌊log(length(A))⌋ × 2“ ”是什么意思

我希望有人能给我解释一下。

 procedure sort(A : array):
        let maxdepth = ⌊log(length(A))⌋ × 2
        introsort(A, maxdepth)

procedure introsort(A, maxdepth):
    n ← length(A)
    p ← partition(A)  // assume this function does pivot selection, p is the final position of the pivot
    if n ≤ 1:
        return  // base case
    else if maxdepth = 0:
        heapsort(A)
    else:
        introsort(A[0:p], maxdepth - 1)
        introsort(A[p+1:n], maxdepth - 1)

Answer 1