Hai nửa phải được sắp xếp trước khi trộn
Sắp xếp trộn (merge sort) chia dãy thành hai phần có độ dài hơn kém nhau không quá 1. Tiếp tục sắp xếp từng phần bằng cùng cách đó. Dãy có không quá một phần tử đã đúng thứ tự, nên là cơ sở dừng.
Khi hai phần đã sắp xếp xong, trộn chúng để nhận một dãy lớn hơn cũng đã sắp xếp. Bước trộn cần **cả hai phần đã có thứ tự**, không chỉ nối hai phần tùy ý.
Theo dõi một dãy sáu phần tử
Với A=[8,3,6,1,7,2], các bước chính là:
| Bước | Dữ liệu |
|---|---|
| Chia lần đầu | [8,3,6] và [1,7,2] |
| Chia tiếp | [8], [3,6]; [1], [7,2] |
| Tới cơ sở | [8], [3], [6], [1], [7], [2] |
| Trộn các phần nhỏ | [3,6] và [2,7] |
| Hai nửa đã xong | [3,6,8] và [1,2,7] |
| Kết hợp cuối | [1,2,3,6,7,8] |
Bước chia tạo bài toán nhỏ; bước trị sắp xếp hai nửa; bước kết hợp trộn kết quả. Khác tìm nhị phân chỉ tiếp tục ở một phía phù hợp, sắp xếp trộn phải giải cả hai phía vì cần giữ mọi phần tử.
Bài luyện
Trong ví dụ, ngay trước phép trộn cuối, hai dãy nào cần có?
Dãy kết quả cuối chưa có trước khi trộn.
Đó là hai nửa đã được sắp xếp.
Hai nửa vừa chia còn chưa có thứ tự.
Hai dãy này bỏ mất nhiều phần tử.
Lời giải
Hai lời gọi nhỏ sắp xếp [8,3,6] thành [3,6,8] và [1,7,2] thành [1,2,7]. Trộn hai kết quả này mới nhận toàn dãy đã sắp xếp.
Bài luyện
Trường hợp nào được trả về ngay trong cơ sở của sắp xếp trộn?
Các phần tử ở giữa vẫn có thể chưa sắp xếp.
Hai phần tử có thể cần đổi thứ tự.
Dãy rỗng hoặc một phần tử đã có thứ tự.
Độ dài chẵn không bảo đảm các giá trị đã đúng thứ tự.
Lời giải
Dãy rỗng không có cặp sai thứ tự; dãy một phần tử cũng không có cặp cần sửa. Vì vậy len(A)<=1 là cơ sở dừng.
Bài luyện
Vì sao bước trị phải sắp xếp cả hai nửa?
Bỏ một nửa sẽ làm mất dữ liệu cần sắp xếp.
Bài toán yêu cầu sắp xếp toàn dãy.
Cần tiếp tục chia nếu nửa đó còn nhiều phần tử.
Mỗi phần đều đóng góp dữ liệu vào kết quả.
Lời giải
Sắp xếp cần giữ nguyên số lượng và các giá trị của toàn dãy. Do đó phải giải cả hai nửa, sau đó trộn; không được loại một phía như tìm một giá trị.
Đang học