Độ phức tạp thời gian và không gian

Độ phức tạp thời gian:

• Trường hợp tốt nhất, trung bình và xấu nhất: O(n log n)
  • Việc xây dựng heap có độ phức tạp O(n), và mỗi lần trích xuất trong số n lần trích xuất tốn O(log n) cho thao tác sift-down. Không có trường hợp đầu vào xấu nào làm giảm hiệu năng của thuật toán.

Độ phức tạp không gian:

• O(1)
  • Heap Sort sắp xếp lại các phần tử bên trong mảng ban đầu và chỉ cần một lượng bộ nhớ bổ sung cố định.

Tóm tắt:

• Heap Sort kết hợp thời gian chạy được đảm bảo là O(n log n) với không gian bổ sung O(1), điều mà Merge Sort và Quick Sort không thể đồng thời đáp ứng.
• Thuật toán không ổn định (các phần tử bằng nhau có thể thay đổi thứ tự tương đối), đây là sự đánh đổi chính của nó.