Isto significa queC(n) ∈ O(n log n)para a segunda fase do heapsort. Para ambas as fases, obtemos O(n) + O(n log n) = O(n log n). Uma análise mais detalhada mostra que a eficiência de tempo do heapsort está, de fato, em (n log n) nos piores e médios casos. Assim, a eficiência de tempo do heapsort cai na mesma classe da mergesort. Ao contrário do último, o heapsort está no local, ou seja, não requer armazenamento extra. Experimentos de tempo em arquivos aleatórios mostram que o heapsort é executado mais lentamente do que o quicksort, mas pode ser competitivo com o mergesort.