Độ 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)
  • Mảng được chia đôi khoảng log n lần, và mỗi cấp thực hiện O(n) thao tác để trộn. Thời gian chạy không phụ thuộc vào thứ tự đầu vào.

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

• O(n)
  • Khác với các thuật toán sắp xếp tại chỗ, Merge Sort tạo các mảng mới khi trộn, vì vậy thuật toán cần thêm bộ nhớ tỷ lệ với kích thước đầu vào.

Tóm tắt:

• Merge Sort nhanh và có hiệu suất ổn định: O(n log n) trong mọi trường hợp.
• Thuật toán ổn định, vì vậy các phần tử bằng nhau vẫn giữ nguyên thứ tự.
• Đổi lại, thuật toán dùng thêm O(n) bộ nhớ để trộn.