Complessità temporale e spaziale

Complessità temporale:

• Caso migliore, medio e peggiore: O(n log n)
  • La costruzione dell’heap richiede O(n) e ciascuna delle n estrazioni costa O(log n) per il ripristino verso il basso. Non esiste un caso di input sfavorevole che ne peggiori le prestazioni.

Complessità spaziale:

• O(1)
  • Heap Sort riordina gli elementi all’interno dell’array originale e richiede solo una quantità costante di memoria aggiuntiva.

Riepilogo:

• Heap Sort combina un tempo di esecuzione garantito di O(n log n) con O(1) di spazio aggiuntivo, una combinazione che né Merge Sort né Quick Sort offrono entrambi.
• Non è stabile (gli elementi uguali possono cambiare ordine relativo), ed è questo il suo principale compromesso.