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)
Re your question on
⌊log(length(A))⌋ × 2
, the⌊...⌋
bit simply meansfloor
, 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-∞
) andint
(round toward0
), 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 oflog
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 asat most Nlog2N comparisons, where N=last-first
but otherwise makes no demands on algorithm choice.