Khi triển khai thuật toán sắp xếp trên các cấu trúc dữ liệu dạng Linked List, tại sao Merge Sort lại được ưu tiên hơn Quicksort về mặt hiệu năng và độ phức tạp bộ nhớ?

Question

Accepted Answer

Phân tích hiệu năng

Quicksort dựa vào việc truy cập ngẫu nhiên (random access) để chọn Pivot và hoán đổi phần tử, điều này rất tốn kém trên Linked List do phải duyệt tuần tự để tìm vị trí node.
Merge Sort hoạt động bằng cách thay đổi các con trỏ (pointers), không yêu cầu cấp phát thêm bộ nhớ phụ (O(1) auxiliary space nếu thực hiện khéo léo) và không cần truy cập ngẫu nhiên.

Ưu điểm của Merge Sort trên Linked List

Tính ổn định (Stability): Giữ nguyên thứ tự của các phần tử có giá trị bằng nhau.
Dự đoán được độ phức tạp: Luôn đạt O(n log n) trong mọi trường hợp, không bị rơi vào trường hợp xấu nhất O(n^2) như Quicksort khi chọn Pivot không tốt.

Ví dụ tư duy
Thay vì sao chép dữ liệu, bạn chỉ cần cập nhật thuộc tính 'next' của các node. Đây là kỹ thuật quan trọng khi xử lý danh sách liên kết lớn trong các hệ thống quản lý bộ nhớ.