Sắp xếp trộn

Trong khoa học máy tính, sắp xếp trộn ("merge sort") là một thuật toán sắp xếp để sắp xếp các danh sách (hoặc bất kỳ cấu trúc dữ liệu nào có thể truy cập tuần tự, v.d. luồng tập tin) theo một trật tự nào đó. Nó được xếp vào thể loại sắp xếp so sánh. Thuật toán này là một ví dụ tương đối điển hình của lối thuật toán chia để trị do John von Neumann đưa ra lần đầu năm 1945. Một thuật toán chi tiết được Goldstine và Neumann đưa ra năm 1948.
Trộn.
Giả sử có hai danh sách đã được sắp xếp formula_1 và formula_2. Ta có thể trộn chúng lại thành một danh sách mới formula_3 được sắp xếp theo cách sau:
Ví dụ: Cho hai danh sách formula_4, quá trình hòa nhập diễn ra như sau:
Trộn tại chỗ.
Giả sử trong danh sách formula_5 có 2 danh sách con kề nhau formula_6 và formula_7 đã được sắp. Ta áp dụng cách trộn tương tự như trên để trộn hai danh sách con vào một danh sách tạm formula_8 rồi trả lại các giá trị của danh sách tạm T về danh sách A. Làm như vậy gọi là trộn tại chỗ.
Trộn từ dưới lên.
Nếu danh sách con chỉ gồm hai phần tử, mỗi nửa của nó gồm một phần tử đương nhiên đã được sắp. Do đó việc trộn tại chỗ hai nửa danh sách này cho danh sách con 2 phân tử được sắp.
Xuất phát từ đầu danh sách formula_9 ta trộn formula_10 với formula_11, formula_12 với formula_13... Khi đó mọi danh sách con gồm hai phần tử của formula_9 đã được sắp. Tiếp tục trộn các danh sách con kế tiếp nhau gồm 2 phần tử thành các danh sách con 4 phần tử... Mỗi lần trộn số các danh sách con cần trộn giảm đi một nửa. Quá trình dừng lại khi số danh sách con chỉ còn một.
Ví dụ: Cho danh sách formula_15
Sắp xếp trộn đệ quy.
Một cách gọi đệ quy của sắp xếp trộn cũng thường được hướng dẫn trong các giáo trình giải thuật.
Để sắp xếp trộn đoạn formula_6 của danh sách formula_5 ta chia đoạn đó thành 2 phần formula_18 và formula_19,trong đó formula_20 tiến hành sắp xếp với mỗi phần rồi trộn chúng lại. Lời gọi thủ tục sắp xếp trộn với formula_5 sẽ cho kết quả là sắp toàn bộ danh sách formula_5
Ví dụ: Cho danh sách formula_23
Trộn các đường tự nhiên.
Như trong phần đánh giá giải thuật, một trong những nhược điểm lớn của thuật toán Trộn trực tiếp là không tận dụng những thông tin về đặc tính của dãy cần sắp xếp. Ví dụ trường hợp dãy đã có thứ tự sẵn. Chính vì vậy, trong thực tế người ta ít dùng thuật toán trộn trực tiếp mà người ta dùng phiên bản cải tiến của nó. Phiên bản này thường được biết với tên gọi thuật toán trộn tự nhiên (Natural Merge sort).
Khái niệm đường chạy.
Để khảo sát thuật toán trộn tự nhiên, trước tiên ta cần định nghĩa khái niệm đường chạy (run):
Giải thuật.
Các bước thực hiện thuật toán trộn tự nhiên như sau:
Ưu và nhược điểm.
Thuật toán trộn tự nhiên khác thuật toán trộn trực tiếp ở chỗ thay vì luôn cứng nhắc phân hoạch theo dãy con có chiều dài k, việc phân hoạch sẽ theo đơn vị là đường chạy. ta chỉ cần biết số đường chạy của a sau lần phân hoạch cuối cùng là có thể biết thời điểm dừng của thuật toán vì dãy đã có thứ tự là dãy chi có một đường chạy.
Một nhược điểm lớn nữa của thuật toán trộn là khi cài đặt thuật toán đòi hỏi thêm không gian bộ nhớ để lưu các dãy phụ b, c. Hạn chế này khó chấp nhận trong thực tế vì các dãy cần sắp xếp thường có kích thước lớn. Vì vậy thuật toán trộn thường được dùng để sắp xếp các cấu trúc dữ liệu khác phù hợp hơn như danh sách liên kết hoặc file.
Mã giả.
Mã giả ngắn gọn.
procedure mergesort(l,r: integer);
var i, j, k, m: integer;
begin 
 if r&gt;l then 
 begin 
 m:=(r+l)shr 1; 
 mergesort(l,m); mergesort(m+1,r);
 for i:= m downto l do b[i]:=a[i];
 for j:=m+1 to r do b[r+m+1-j]:=a[j];
 for k:=l to r do 
 if b[i] &lt; b[j] then 
 begin a[k]:=b[i]; i:=i+1 end
 else 
 begin a[k]:=b[j]; j:=j-1 end;
 end;
end; 
Trộn đệ quy.
Ngôn ngữ C++