Sắp xếp trộn (merge sort) trong Python
Bài 17/20 · Chương 23
Cấu trúc dữ liệu và giải thuật
- 9 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 12
Sắp xếp trộn (merge sort) là thuật toán sắp xếp chia đôi dãy, sắp xếp từng nửa bằng đệ quy, rồi trộn hai nửa đã xếp thành một dãy. Bạn dùng nó khi cần tốc độ đều đặn với dãy dài, ví dụ gộp lịch sử thao tác từ nhiều thiết bị thành một dòng thời gian. Số bước không tệ đi dù đầu vào có thứ tự nào.
Cần biết trước: đệ quy, cắt list bằng lát cắt và sắp xếp chèn.
Hai con trỏ trộn hai nửa đã xếp
Máy tính và điện thoại mỗi nơi ghi thời điểm (giây) các thao tác của mình theo thứ tự tăng dần. Để có một dòng thời gian chung, bạn đặt một con trỏ i ở đầu list thứ nhất, một con trỏ j ở đầu list thứ hai. Mỗi bước so hai phần tử đang được trỏ, lấy phần tử nhỏ hơn, rồi tiến con trỏ đó lên một ô:
def tron(trai, phai):
ket_qua = []
i, j = 0, 0
while i < len(trai) and j < len(phai):
if trai[i] <= phai[j]:
ket_qua.append(trai[i])
i += 1
else:
ket_qua.append(phai[j])
j += 1
ket_qua.extend(trai[i:])
ket_qua.extend(phai[j:])
return ket_qua
print(tron([3, 8, 15], [5, 6, 20, 31]))KẾT QUẢ
[3, 5, 6, 8, 15, 20, 31]Hai con trỏ (two pointers) là hai chỉ số cùng đi trên dữ liệu. Trong phép trộn, mỗi con trỏ chỉ tiến, không bao giờ lùi. Vì cả hai list đã xếp, phần tử nhỏ nhất chưa lấy luôn nằm ở một trong hai chỗ đang được trỏ, nên mỗi phép so lấy ra đúng một phần tử. Vòng while dừng khi một list hết. Phần còn lại của list kia đã xếp và lớn hơn mọi thứ đã lấy, nên hai dòng extend() nối thẳng vào cuối mà không cần so thêm. Bài trộn hai list đã sắp xếp luyện riêng việc trộn này.
Chia để trị bằng đệ quy
Trộn chỉ làm được khi hai nửa đã xếp. Merge sort có được hai nửa đó bằng chính nó: chia list ở giữa, gọi đệ quy cho mỗi nửa, rồi trộn. Điều kiện dừng là list rỗng hoặc chỉ có một phần tử, vì list như vậy đã xếp sẵn. Cách làm ba bước chia, giải từng phần, ghép kết quả gọi là chia để trị. Hàm dưới đây chỉ in các lần chia, mỗi tầng thụt vào thêm hai dấu cách:
def chia(ds, thut=""):
print(thut + str(ds))
if len(ds) > 1:
giua = len(ds) // 2
chia(ds[:giua], thut + " ")
chia(ds[giua:], thut + " ")
chia([38, 5, 21, 5, 12])KẾT QUẢ
[38, 5, 21, 5, 12]
[38, 5]
[38]
[5]
[21, 5, 12]
[21]
[5, 12]
[5]
[12]giua = 5 // 2 bằng 2, nên nửa trái là [38, 5], nửa phải là [21, 5, 12]. Nửa trái được chia hết trước rồi mới tới nửa phải, đúng thứ tự Python chạy hai lời gọi đệ quy. Ghép phần trộn vào sau hai lời gọi là có merge sort đầy đủ:
def merge_sort(ds):
if len(ds) <= 1:
return ds
giua = len(ds) // 2
trai, phai = merge_sort(ds[:giua]), merge_sort(ds[giua:])
kq, i, j = [], 0, 0
while i < len(trai) and j < len(phai):
if trai[i] <= phai[j]:
kq.append(trai[i])
i += 1
else:
kq.append(phai[j])
j += 1
return kq + trai[i:] + phai[j:]
print(merge_sort([38, 5, 21, 5, 12]))KẾT QUẢ
[5, 5, 12, 21, 38]Lần trộn đầu tiên xảy ra ở đáy cây chia: [38] với [5] thành [5, 38]. Lần cuối gộp [5, 38] với [5, 12, 21]. Biểu thức kq + trai[i:] + phai[j:] làm đúng việc của hai dòng extend() ở mục trước. Mỗi lát cắt tạo một list mới, nên list của nơi gọi không bị đổi.
Vì sao luôn là O(n log n)
Mỗi lần chia đôi, độ dài giảm một nửa, nên sau khoảng log₂(n) tầng chia mọi đoạn chỉ còn một phần tử. Ở mỗi tầng, các lần trộn cộng lại đi qua mỗi phần tử đúng một lần, nên tốn không quá n phép so. Hàm dưới đây đếm số tầng bằng đệ quy theo nửa dài hơn:
def so_tang(n):
if n <= 1:
return 0
return 1 + so_tang(n - n // 2)
for n in [8, 1000, 1000000]:
tang = so_tang(n)
print(n, "phần tử:", tang, "tầng, tối đa", n * tang, "phép so")KẾT QUẢ
8 phần tử: 3 tầng, tối đa 24 phép so
1000 phần tử: 10 tầng, tối đa 10000 phép so
1000000 phần tử: 20 tầng, tối đa 20000000 phép soMột triệu phần tử chỉ cần 20 tầng. Sắp xếp chèn với list xếp ngược cùng cỡ phải dịch khoảng 500 tỷ lần, còn merge sort tốn không quá 20 triệu phép so, dù list vào đã xếp, xếp ngược hay lộn xộn. Đó là O(n log n) theo cách đếm của bài Big O. Đổi lại, merge sort không sớm dừng được với list gần đúng thứ tự như sắp xếp chèn.
Ổn định và cái giá bộ nhớ
Phép so <= lấy phần tử bên trái khi hai phần tử bằng nhau. Phần tử bên trái đứng trước trong list gốc, nên các phần tử bằng nhau giữ thứ tự cũ, tức merge sort ổn định. Xếp các thao tác (ten, giay) theo giây:
def xep_giay(ds):
if len(ds) <= 1:
return ds
giua = len(ds) // 2
trai, phai = xep_giay(ds[:giua]), xep_giay(ds[giua:])
kq, i, j = [], 0, 0
while i < len(trai) and j < len(phai):
if trai[i][1] <= phai[j][1]:
kq.append(trai[i])
i += 1
else:
kq.append(phai[j])
j += 1
return kq + trai[i:] + phai[j:]
print(xep_giay([("lưu", 9), ("mở", 4), ("sửa", 9), ("đóng", 4)]))KẾT QUẢ
[('mở', 4), ('đóng', 4), ('lưu', 9), ('sửa', 9)]Thao tác "mở" có trước "đóng" cùng giây 4, và vẫn đứng trước sau khi xếp. Đổi trai[i][1] <= phai[j][1] thành trai[i][1] < phai[j][1] rồi chạy lại: dòng kết quả in ('đóng', 4), ('mở', 4), thứ tự cũ đã mất. Cái giá của merge sort là bộ nhớ: mỗi lần trộn tạo list mới, nên thuật toán cần thêm O(n) chỗ nhớ, khác ba thuật toán chỉ đổi chỗ bên trong list ở các bài trước.
Kiểm tra nhanh
Hàm
troncủa bài trộn[2, 9]với[4, 5, 11]. Khi vòngwhiledừng,ivàjbằng bao nhiêu?i = 2,j = 2i = 2,j = 3i = 1,j = 3
Những điều nào đúng với merge sort của bài?
- List đã xếp và list xếp ngược cùng độ dài có cùng số tầng chia đôi
- List đã xếp chỉ tốn O(n) phép so, như sắp xếp chèn
- Mỗi lần trộn tạo list mới, nên cần thêm bộ nhớ
- Đổi
<=thành<vẫn giữ thứ tự cũ của phần tử bằng nhau
Điều kiện dừng viết
if len(ds) == 0: return ds. Gọimerge_sort([38, 5])thì sao?- Trả về
[5, 38] - Báo lỗi RecursionError
- Trả về
[]
- Trả về
Bỏ hai dòng
extend()khỏi hàmtron. Trộn[3, 8, 15]với[5, 6, 20, 31]thì trả về gì?[3, 5, 6, 8, 15, 20, 31][3, 5, 6, 8][3, 5, 6, 8, 15]
Bài tập
Xếp lịch sử thao tác và đếm phép so
Lịch sử thao tác ghi thời điểm (giây) của từng thao tác. Viết thân hàm merge_sort_dem(ds) xếp tăng dần bằng merge sort và đếm số phép so hai phần tử khi trộn. List có từ hai phần tử thì chia ở giua = len(ds) // 2 thành ds[:giua] và ds[giua:], rồi xếp từng nửa bằng đệ quy. Trộn bằng hai con trỏ: hai số bằng nhau thì lấy bên trái trước, một nửa hết thì nối phần còn lại của nửa kia mà không so thêm. Không dùng sorted() hay sort(), và không sửa ds.
Ví dụ: merge_sort_dem([38, 5, 21, 5, 12]) trả về ([5, 5, 12, 21, 38], 8).
Trả về: list đã xếp và tổng số phép so của mọi lần trộn, một tuple.
def merge_sort_dem(ds):
pass # Viết thân hàm thay cho dòng nàyTóm tắt
Merge sort chia list ở
len(ds) // 2, xếp hai nửa bằng đệ quy rồi trộn: cách làm chia để trị.Điều kiện dừng là
len(ds) <= 1; dừng ở list rỗng thì list một phần tử chia mãi và báoRecursionError.Trộn bằng hai con trỏ chỉ tiến; một nửa hết thì nối phần còn lại mà không so thêm.
Có khoảng log₂(n) tầng, mỗi tầng không quá
nphép so: luôn O(n log n), kể cả với list đã xếp.Lấy bên trái khi bằng nhau (
<=) giữ thuật toán ổn định; mỗi lần trộn tạo list mới nên cần thêm O(n) bộ nhớ.
Câu hỏi thường gặp
Sắp xếp trộn (merge sort) là gì và khác sắp xếp nhanh ở đâu?
Merge sort chia đôi đúng ở giữa rồi làm phần việc chính khi trộn, nên luôn O(n log n) và ổn định, đổi lại cần thêm bộ nhớ. Sắp xếp nhanh làm phần việc chính khi chia quanh một phần tử chốt, thường nhanh hơn, nhưng có thể chậm tới O(n²) khi chốt chọn kém.
Có viết được merge sort trong Python mà không dùng đệ quy không?
Có. Bản không đệ quy trộn từ dưới lên: trộn từng cặp đoạn dài 1 thành đoạn dài 2, rồi đoạn dài 2 thành đoạn dài 4, cứ thế cho tới khi chỉ còn một đoạn. Cách này tránh giới hạn tầng gọi của đệ quy, nhưng chỗ chia có thể khác bản đệ quy khi độ dài không phải lũy thừa của 2.
Vì sao merge sort luôn có độ phức tạp O(n log n)?
Vì cách chia không phụ thuộc giá trị: list nào cũng bị chia đôi khoảng log₂(n) lần, và mỗi tầng trộn mỗi phần tử một lần. Thứ tự đầu vào chỉ đổi số phép so trong từng lần trộn, không đổi số tầng. Bài Big O giải thích cách đọc các ký hiệu này.
Hàm sorted() của Python có dùng sắp xếp trộn không?
Có, một phần. sorted() và sort() dùng Timsort, thuật toán tìm các đoạn đã có thứ tự sẵn trong dữ liệu, kéo dài đoạn ngắn bằng sắp xếp chèn, rồi trộn các đoạn với nhau. Bài thuật toán sắp xếp so sánh Timsort với các thuật toán tự viết.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.