Sắp xếp trộn¶

Sắp xếp trộn là một thuật toán sắp xếp dựa trên chiến lược chia để trị, bao gồm các giai đoạn "chia" và "trộn" được thể hiện trong hình dưới đây.

Giai đoạn chia: Tách mảng đệ quy tại trung điểm, giảm bài toán sắp xếp một mảng dài thành bài toán sắp xếp các mảng ngắn hơn.
Giai đoạn trộn: Khi một mảng con có độ dài bằng 1, dừng chia và bắt đầu trộn, liên tục kết hợp các mảng con đã sắp xếp ngắn hơn ở bên trái và bên phải thành một mảng đã sắp xếp dài hơn cho đến khi quá trình hoàn tất.

Quy trình thuật toán¶

Như được thể hiện trong hình dưới đây, "giai đoạn chia" tách đệ quy mảng từ trung điểm thành hai mảng con từ trên xuống dưới.

Tính trung điểm của mảng mid, chia đệ quy mảng con bên trái (khoảng [left, mid]) và mảng con bên phải (khoảng [mid + 1, right]).
Lặp lại bước 1. một cách đệ quy cho đến khi mảng con có độ dài bằng 1.

"Giai đoạn trộn" thực hiện trộn các mảng con bên trái và bên phải thành một mảng đã sắp xếp từ dưới lên trên. Lưu ý rằng việc trộn bắt đầu từ các mảng con có độ dài bằng 1, do đó mọi mảng con tham gia vào giai đoạn này đều đã được sắp xếp.

Thứ tự đệ quy của sắp xếp trộn nhất quán với phép duyệt hậu thứ tự của cây nhị phân.

Duyệt hậu thứ tự: Đầu tiên duyệt đệ quy cây con bên trái, sau đó duyệt đệ quy cây con bên phải, và cuối cùng xử lý nút gốc.
Sắp xếp trộn: Đầu tiên xử lý đệ quy mảng con bên trái, sau đó xử lý đệ quy mảng con bên phải, và cuối cùng thực hiện thao tác trộn.

Mã nguồn triển khai của sắp xếp trộn được thể hiện dưới đây. Lưu ý rằng khoảng cần trộn trong nums là [left, right], trong khi khoảng tương ứng trong tmp là [0, right - left].

[file]{merge_sort}-[class]{}-[func]{merge_sort}

Đặc điểm của thuật toán¶

Độ phức tạp thời gian là \(O(n \log n)\), sắp xếp trộn không thích ứng: Giai đoạn chia tạo ra một cây đệ quy có chiều cao \(\log n\), và tổng số thao tác thực hiện trong quá trình trộn ở mỗi mức là \(n\), do đó độ phức tạp thời gian tổng thể là \(O(n \log n)\).
Độ phức tạp không gian là \(O(n)\), sắp xếp trộn không phải là sắp xếp tại chỗ: Độ sâu đệ quy là \(\log n\), sử dụng \(O(\log n)\) không gian khung ngăn xếp. Thao tác trộn yêu cầu một mảng phụ trợ, sử dụng \(O(n)\) không gian bổ sung.
Sắp xếp ổn định: Trong quá trình trộn, thứ tự tương đối của các phần tử bằng nhau không thay đổi.

Sắp xếp danh sách liên kết¶

Đối với danh sách liên kết, sắp xếp trộn có lợi thế lớn so với các thuật toán sắp xếp khác, và nó có thể giảm độ phức tạp không gian của tác vụ sắp xếp xuống còn \(O(1)\).

Giai đoạn chia: Có thể sử dụng phép lặp thay vì đệ quy để tách danh sách liên kết, từ đó loại bỏ không gian khung ngăn xếp do đệ quy sử dụng.
Giai đoạn trộn: Trong danh sách liên kết, việc chèn và xóa nút chỉ yêu cầu cập nhật con trỏ, do đó giai đoạn trộn (trộn hai danh sách liên kết đã sắp xếp ngắn hơn thành một danh sách liên kết đã sắp xếp dài hơn) không yêu cầu tạo thêm danh sách liên kết bổ sung.

Các chi tiết triển khai cụ thể khá phức tạp, bạn đọc quan tâm có thể tham khảo các tài liệu liên quan để tìm hiểu thêm.