Tổng quan
Merge Sort là thuật toán chia-để-trị ổn định: chia mảng thành hai nửa, sắp xếp đệ quy từng nửa, rồi trộn hai nửa đã sắp thành một. Nó đảm bảo thời gian O(n log n) bất kể đầu vào.
Merge Sort hoạt động thế nào?
- Chia mảng thành hai nửa tại điểm giữa.
- Sắp xếp đệ quy nửa trái và nửa phải.
- Trộn hai nửa đã sắp bằng cách liên tục lấy phần tử đầu nhỏ hơn.
- Việc trộn hai nửa ở mức cao nhất cho ra mảng đã sắp hoàn chỉnh.
Khi nào nên dùng?
- Khi cần đảm bảo O(n log n) ở trường hợp xấu nhất.
- Khi cần tính ổn định (ví dụ sắp bản ghi theo khóa phụ).
- Sắp xếp ngoài với dữ liệu quá lớn so với bộ nhớ, và sắp danh sách liên kết.
Phân tích độ phức tạp
Mảng chia thành log n mức, mỗi mức tốn O(n) để trộn, cho O(n log n) trong mọi trường hợp. Đánh đổi là cần O(n) bộ nhớ phụ cho vùng đệm trộn. Merge Sort ổn định.
Câu hỏi thường gặp
Vì sao Merge Sort cần bộ nhớ phụ?
Trộn hai nửa đã sắp ngay tại chỗ rất khó làm hiệu quả, nên phiên bản chuẩn sao chép phần tử vào vùng đệm tạm kích thước O(n) khi trộn.
Merge Sort có luôn O(n log n) không?
Có — độ sâu đệ quy và chi phí trộn mỗi mức không phụ thuộc thứ tự đầu vào, nên tốt nhất, trung bình và xấu nhất đều O(n log n).