Ý tưởng
Gọi k là chiều dài của một dãy con
Phân chia dãy ban đầu thành các dãy con có độ dài k, các dãy con này được phân phối luân phiên vào 2 dãy phụ.
Trộn từng cặp dãy con của 2 dãy phụ thành một dãy con của dãy ban đầu, cuối cùng ta sẽ thu được dãy ban đầu có số lượng dãy con giảm phân nửa.
Tăng độ dài k, lặp lại qui trình trên sau một số bước ta sẽ thu được dãy chỉ gồm 1 dãy con, tức là dãy ban đầu đã được sắp xếp.
Giải thuật
Bước 1: k = 1; // k là chiều dài của dãy con trong bước hiện hành
Bước 2:
Tách dãy a1, a2,…, an thành 2 dãy b, c theo nguyên tắc luân phiên
từng nhóm k phần tử:
b = a1,…, ak, a2k+1, …,a3k,…
c = ak+1,…, a2k+1, a3k+1, …,a4k,…
Bước 3: Trộn từng cặp dãy con gồm k phần tử của 2 dãy b, c vào a.
Bước 4: k = k*2;
Nếu k < n : Lặp lại bước 2.
Ngược lại: Dừng.
Thuật toán Natural Merge Sort khác thuật toán Merge Sort ở 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 sao 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 chỉ có một đường chạy.
Thuật toán
Bước 1: r = 0; // r dùng để đếm số đường chạy.
từng đường chạy.
Bước 21:
Phân phối cho b một đường chạy; r = r + 1;
Nếu a còn phần tử chưa phân phối
Phân phối cho c một đường chạy; r = r + 1;
Bước 22:
Nếu a còn phần tử: quay lại bước 21.
Bước 3: Trộn từng cặp đường chạy của 2 dãy b, c vào a.
Bước 4: Nếu r ≥ 2 : Lặp lại bước 2.