[SOLVED] STL std::sort() uses Introsort, but how does it work?

STL std::sort() uses Introsort, but how does it work?

I don't really get the Introsort algorithm. As you can see I added the pseudocode of it. What is meant by the maxdepth?

What does that mean " ⌊log(length(A))⌋ × 2"

I hope someone can explain it to me.

 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)

Solution

Re your question on ⌊log(length(A))⌋ × 2, the ⌊...⌋ bit simply means floor, the highest integer less than or equal to the value.

In a less mathematical language, it would be int(log(length(A))) * 2.

And just in case someone brings up the difference between floor (round toward -∞) and int (round toward 0), it's irrelevant here as the length must be a non-negative integer. You'll still run into mathematical trouble if the length is zero but that's an exceptional case since it probably doesn't need sorting :-)

As to why maxdepth exists, this is obviously an algorithm based on trees - the use of log also supports this since the depth of a balanced tree tends to be proportional to the logarithm of the number of nodes in it.

What seems to be happening is that, if the introsort gets beyond a certain depth, it just switches over to heapsort for the remainder.

And, just one minor note: std::sort() is not required to use Introsort (as your title seems to imply), the standard mandates behaviour such as at most Nlog₂N comparisons, where N=last-first but otherwise makes no demands on algorithm choice.