Skip to main content

Merge Sort

Cập nhật: 2026-08-10

Mục lục​

1. Ý tưởng của Merge Sort​

Merge Sort theo chiến lược chia để trị (divide and conquer): chia mảng làm đôi liên tục cho đến khi mỗi đoạn chỉ còn 1 phần tử (đã hiển nhiên "sắp xếp xong"), rồi trộn (merge) dần các đoạn đã sắp xếp lại với nhau theo thứ tự tăng dần, từ nhỏ đến lớn, cho tới khi trộn lại thành mảng hoàn chỉnh.

Bước trộn là trái tim của thuật toán: với hai đoạn con đã sắp xếp, ta dùng hai con trỏ i và j để luôn lấy ra phần tử nhỏ hơn giữa hai đầu đoạn, ghi vào một mảng tạm, rồi copy ngược lại vào mảng gốc.

2. Xem thuật toán chạy từng bước​

Bấm Chạy để xem animation tự động, hoặc dùng Lùi / Tiến để đi qua từng bước một. Dải màu tím bên dưới hàng pin thể hiện đoạn con đang được xử lý (chia hoặc trộn); cột màu tím đậm là phần tử vừa được ghi vào đúng vị trí sau khi trộn.

SORTING · TRỰC QUAN HOÁ

Merge Sort

LẦN TRỘN 0/9SO SÁNH 0/22GHI 0/34
0
 
1
 
2
 
3
 
4
 
5
 
6
 
7
 
8
 
9
 

Gọi merge_sort trên đoạn [0, 9].

merge_sort.pyO(n log n) time · O(n) space
1def merge_sort(lo, hi):
2 if lo >= hi: return
3 mid = (lo + hi) // 2
4 merge_sort(lo, mid)
5 merge_sort(mid + 1, hi)
6 merge(lo, mid, hi)
7
8def merge(lo, mid, hi):
9 i, j = lo, mid + 1
10 for k in range(lo, hi + 1):
11 if j > hi or (i <= mid and arr[i] <= arr[j]):
12 temp[k] = arr[i]; i += 1
13 else:
14 temp[k] = arr[j]; j += 1
15 arr[lo:hi + 1] = temp[lo:hi + 1]
Bước 1/113

3. Độ phức tạp​

Merge Sort
Thời gian (mọi trường hợp)O(n log n)
Bộ nhớ phụO(n) — cần mảng tạm để trộn
Ổn định (stable)Có

Khác với Selection Sort hay Bubble Sort, Merge Sort đảm bảo O(n log n) trong mọi trường hợp (không phụ thuộc dữ liệu đầu vào), đổi lại phải trả thêm chi phí bộ nhớ O(n) cho mảng tạm. Đây cũng là thuật toán nền tảng cho external sort (sắp xếp dữ liệu không vừa RAM) và là một phần của Timsort — thuật toán sort mặc định của Python và Java.