Introsort only adds a depth check and size check to each recursion, that's only a couple of instructions with little memory access.