Divide and conquer là một trong số những mẫu thiết kế giải thuật chung được nhiều người biết đến nhất, và merge sort là một ứng dụng hay được tạo ra trên nền algorithm này. Trước khi đến với Merge Sort, chúng ta hãy tìm hiểu về Divide and Conquer.
Mục lục
Divide and conquer technique (typical case)
Các giải thuật devide and conquer hoạt động theo các bước sau:
1. Problem sẽ được chia thành nhiều cụm nhỏ, nên có kích thước bằng nhau.
2. Chúng ta sẽ xử lý tuần tử các problem nhỏ, đa số dùng đệ quy.
3. Trong một số trường hợp, kết quả của chúng sẽ được gộp để có kết quả.

Giải thuật Merge Sort
Merge sort là một ví dụ của giải thuật divide and conquer này. Sau khi chia đủ nhỏ, merge sort sẽ gộp hai dữ liệu đã sort thành một dữ liệu lớn hơn.

Độ phức tạp của merge sort
Với n là số mũ của 2 và C(n) là số lần so sánh n phần tử, ta có:
C(n) = 2C(n/2) + Cmerge(n) for n>1, C(1) = 0
Tại sao như vậy?
Ví dụ: chúng ta cần sử dụng merge sort đế sort 8 chữ số sau theo thứ tự tăng dần:
Bước 1: Chia ra (divide)
Lần chia 1: 1 dãy số
108 15 50 4 8 42 23 16
Lần chia 2: 2 dãy số
(108 15 50 4) (8 42 23 16)
Lần chia 3: 4 dãy số
(108 15) (50 4) (8 42) (23 16)
Lần chia 4: 8 dãy số
(108) (15) (50) (4) (8) (42) (23) (16)
Trong đó: C(n/2) là số so sánh chúng ta cần khi chia nửa số hạng, và cần 2 lần như vậy cho mỗi bước. Do đó ta có 2C(n/2)
Bước 2: Merge (conquer)
Lần gộp 1 – Số lần so sánh mỗi cặp tối đa: 1
(108) (15) (50) (4) (8) (42) (23) (16)
Lần gộp 2 – Số lần so sánh mỗi cặp tối đa: 1
(15 108) (4 50) (8 42) (16 23)
Lần gộp 3 – Số lần so sánh mỗi cặp tối đa: 4
(4 15 50 108) (8 16 23 32)
Ở bước này, xét trong hai cặp (15 108) và (4 50), merge sort sẽ lấy từng phần tử bé nhất của mỗi list (hoặc array) so sánh với nhau.
Cho A {15, 108} và B {4, 50}, các bước so sánh theo tuần tự:
15 và 4: 4 nhỏ hơn → {4} ; A {15, 108} ; B {50}
15 và 50: 15 nhỏ hơn → {4, 15} ; A {108} ; B {50}
108 và 50: 50 nhỏ hơn → {4, 15, 50} ; A {108} ; B {}
Chỉ còn 108 → {4, 15, 50, 108}
Tương tự với dãy array còn lại.
Lần gộp 4 – Số lần so sánh mỗi cặp tối đa: 8
(4 8 15 16 23 32 50 108)
Do vậy trong trường hợp xấu nhất, ta có n-1 lần so sánh.
Do đó ta có C(n) = 2C(n/2) + n -1 với n >1
Rút gọn lại: C(n) = 2C(n/2) + n
Giải theo Master Theorem, ta có kết quả O(nlogn)
Code của Merge Sort
procedure mergesort(1,r: integer);
var i, j, k, m : integer;
begin
if r-1>0 then
begin
m:=(r+1)/2; mergesort(1,m); mergesort(m+1,r);
for i := m downto 1 do b[i] := a[j];
for j :=m+1 to r do b[r+m+1-j] := a[j];
for k :=1 to r do
if b[i] < b[j] then
begin a[k] := b[i] ; i := i+1 end
else begin a[k] := b[j]; j:= j-1 end;
end;
end;
Ưu điểm và nhước điểm của Merge Sort
Ưu: Độ phức tạp tốt hơn so với Insertion Sort, Selection Sort, Interchange Sort
Nhược: Cần thêm bộ nhớ để chứa một mảng thứ 3
Tham khảo thêm về Merge Sort tại video ngắn sau đây:
Mai Nguyên Vũ
Tôi có kinh nghiệm trong việc tạo ra những web vui vui phục vụ mục đích cá nhân và thoả mãn nhu cầu tìm kiếm thông tin từ người dùng. Tôi nhận ra nhiều trang web cung cấp thông tin chưa thực sự cá nhân hoá những thắc mắc của người dùng. Stream Hub là một sản phẩm "vui vui" tôi tạo ra có sứ mệnh giải quyết vấn đề đó.