Merge sort tr
Merge sort tr
ự
ự
c ti
c ti
ế
ế
p
p
41
Merge sort tr
Merge sort tr
ự
ự
c ti
c ti
ế
ế
p
p
 Đánh giá thuật toán:
- Chi phí thực hiện MergeSort là O(nlgn)
- Nhược điểm: Không tận dụng được đặc tính của
dãy cần sắp xếp. Ví dụ: Trường hợp dãy đã có sẵn
thứ tự
-  Thuật toán Merge sort cải tiến: Phương pháp
trộn tự nhiên (Natural Merge sort)
42
Natural Merge sort
Natural Merge sort

B3:a=[1,2,4,5,8,10,12,17,1,3,4,4,24]
Natural Merge sort
Natural Merge sort
B3:a=[1,2,4,5,8,10,12,17,1,3,4,4,24]
(1,2,4,5,8,10,12,17);(1,3,4,4,24) r=2 B2
B2: b=[(1,2,4,5,8,10,12,17)]
c=[(1,3,4,4,24)]
B3: a=[1,1,2,3,4,4,4,5,8,10,12,17,24]
(1,1,2,3,4,4,4,5,8,10,12,17,24) r=1  Dừng
Natural Merge sort
Natural Merge sort
 Ưu và nhược điểm:
- Thuật toán trộn tự nhiên tận dụng được các đường
chạy tự nhiên của dãy
- Tuy nhiên, trộn tự nhiên đòi hỏi không gian bộ nhớ
để lưu các dãy phụ b, c
- Thuật toán trộn tự nhiên thường ứng dụng trong
các cấu trúc dữ liệu là danh sách liên kết hoặc file
Polyphase Merge sort
Polyphase Merge sort
 Trộn đa lối cân bằng:
Thay vì thực hiện 2 giai đoạn: Phân phối và trộn
như Thuật toán Merge sort thông thường, trộn đa
pha cân bằng chỉ cần thực hiện 1 giai đoạn trộn
- Ti
ế
t ki
ệ
m ½ chi phí
- C

a2:NULL
a3: NULL
 Run =1. Kết thúc