t = b; //vị trí bắt đầu mảng gộp ở mảng X, biến chạy trên X while(i <= m && j <= n){ if(K[i] < K[j]){ X[t++] = K[i++] }else{ X[t++] = K[j++]; } }
//đến bước này, 1 trong 2 mảng con đã hết khoá if(i>m){ //Mảng con 1 hết khoá //-> cho hết khoá ở mảng 2 xuống for(;j <= n;){ X[t++] = K[j++]; } }else{ for(;i <= n;){ X[t++] = K[i++]; } } }
//Hàm này thực hiện hoà nhập từng cặp mạch có độ dài là h kế cận nhau // với dãy có n phần tử từ mảng K qua mảng X MPASS(K, X, n, h){ i = 0; while(i + 2*h <= n){ Merge(K, i, i + h - 1, i + 2*h - 1, X); i = i + 2*h; }
if(i + h < n){ Merge(K, i, i + h - 1, n-1, X); }else{ for(;i X[i++] = K[i++]; } } }
//Hàm MPASS trên sẽ được gọi trong hàm chính sau STRAIGHT_MSORT(K, n){ /* Ở đây sẽ dùng 1 mảng phụ X[n], 2 mảng được dùng luân phiên H lưu kích thước mạch, sau mỗi 1 lần gọi MPASS thì h được nhân đôi */
h = 1; while(h < n){ MPASS(K, X, n, h); h = h*2; MPASS(X, K, n, h); h = h*2; } }
Đánh giá giải thuật: Ta thấy với Hàm MPASS, mỗi 1 lượt gọi thì các phần tử ở K sẽ được chuyển hết xuống X, vậy chi phí thời gian cho 1 lượt có cấp O(n).
Với hàm STRAIGHT_MSORT thì số lượt gọi hàm MPASS sẽ là log2n lần,
