Quicksort ở bài trước nhanh nhưng có một mặt tối: pivot dở gặp mảng đã sắp thì thành O(n²) và tràn ngăn xếp. Merge sort là câu trả lời "chắc chắn" cho nỗi lo đó — nó O(n log n) trên mọi đầu vào, không có ca xấu nào. Câu hỏi tự nhiên: nếu cả hai đều O(n log n), thì merge sort có nhanh bằng quicksort không? Bài này đo, và câu trả lời — cùng cách tôi tìm ra vì sao — là một bài học về việc big-O giấu điều gì và trực giác của tôi chỉ nhầm thủ phạm ra sao.
Merge sort: chia, sắp, rồi trộn
Merge sort cũng chia để trị, nhưng theo hướng ngược với quicksort. Nó chia mảng làm đôi một cách máy móc (đúng giữa, không cần chọn pivot), đệ quy sắp hai nửa, rồi trộn (merge) hai nửa đã sắp thành một dãy sắp hoàn chỉnh. Bước trộn là trái tim: đặt hai con trỏ ở đầu hai nửa, mỗi lần chép phần tử nhỏ hơn ra một mảng đệm, cứ thế cho tới hết. Vì việc chia luôn cân đúng một nửa, cây đệ quy luôn sâu đúng log n tầng, và mỗi tầng làm O(n) việc trộn — nên tổng luôn là O(n log n), bất kể đầu vào. Không có mảng đã sắp nào, không có kẻ tấn công nào, làm nó chậm đi được.
Merge sort có hai phẩm chất mà quicksort không có. Nó ổn định (stable): hai phần tử có khóa bằng nhau giữ nguyên thứ tự gốc — cực kỳ quan trọng khi bạn sắp theo nhiều tiêu chí liên tiếp. Và nó không có ca xấu O(n²). Cái giá đổi lại: nó không sắp tại chỗ, cần O(n) bộ nhớ phụ để trộn. Câu hỏi tôi mang vào phép đo: cái giá bộ nhớ đó khiến merge sort chậm hơn quicksort bao nhiêu, và cái chậm ấy nằm ở đâu?
Đo: cùng O(n log n), mà chậm hơn 1,25 lần
Tôi cài merge sort (dùng một mảng đệm tái sử dụng) và quicksort trung vị-của-ba (từ bài trước), sắp cùng hai triệu số ngẫu nhiên:
quicksort (sắp tại chỗ) : 98 ms
merge sort (một đệm tái dùng) : 121 ms = 1,25 lần quicksort
Cùng một độ phức tạp O(n log n), mà chênh nhau 25%. Big-O nói hai thuật toán này "như nhau"; đồng hồ nói không. Đây chính là điều ký hiệu tiệm cận giấu đi: nó đếm số phép so sánh (cả hai đều ~n log n phép), nhưng không đếm những gì mỗi phép kéo theo. Và tôi tưởng mình biết ngay thủ phạm.
Một lần tôi đo hớ: tôi nhầm thủ phạm là malloc
Trực giác của tôi bật ra lập tức: merge sort chậm hơn vì nó cấp phát bộ nhớ — cái mảng đệm. Ai cũng biết malloc trong vòng lặp nóng là kẻ giết hiệu năng. Tôi đoán rằng nếu tôi viết một phiên bản merge sort ngây thơ hơn — cấp phát một mảng đệm mới trong mỗi lần trộn thay vì dùng một đệm chung — thì nó sẽ chậm thảm hại, và đó sẽ là bằng chứng cho "malloc giết hiệu năng".
Tôi đo phiên bản malloc-mỗi-lần đó:
merge sort (một đệm tái dùng) : 121 ms
merge sort (malloc mỗi lần trộn) : 128 ms = chỉ chậm hơn 6%
Chỉ 6%. Không hề là thảm họa tôi chờ đợi. Hóa ra bộ cấp phát của glibc có một đường nhanh cho những lần cấp phát nhỏ cùng cỡ lặp đi lặp lại (tcache), nên malloc trong merge rẻ hơn nhiều so với danh tiếng của nó. Trực giác của tôi đã chỉ nhầm thủ phạm. Vậy 23 mili giây chênh giữa quicksort và merge sort đến từ đâu, nếu không phải malloc?
Phân rã con số cho câu trả lời sạch sẽ. Phiên bản merge "một đệm tái dùng" không cấp phát trong vòng nóng, mà vẫn chậm hơn quicksort 23 mili giây. Phiên bản malloc-mỗi-lần chỉ cộng thêm 7 mili giây nữa. Nghĩa là: chi phí chép dữ liệu (23 ms) lớn hơn chi phí cấp phát (7 ms) gấp ba. Thủ phạm thật là việc merge sort, ở mỗi tầng trong log n tầng, phải chép cả n phần tử ra mảng đệm rồi chép ngược về — đó là n log n lượt di chuyển bộ nhớ mà quicksort hoàn toàn không phải trả, vì quicksort phân hoạch ngay tại chỗ trên mảng gốc, chẳng chép đi đâu cả. Bài học đo lường: khi một thứ chậm hơn, đừng tin thủ phạm đầu tiên trực giác chỉ ra — đo để tách bạch, vì cái đắt thường không phải cái bạn nghĩ. Ở đây tôi suýt viết cả một đoạn đổ tội cho malloc, trong khi đồng hồ chỉ thẳng vào việc di chuyển dữ liệu.
Vậy dùng merge sort để làm gì?
Nếu merge sort chậm hơn quicksort, sao còn dùng? Vì tốc độ thô không phải giá trị của nó. Tôi đo hai thứ khác. Thứ nhất, ổn định: tôi sắp một triệu bản ghi có khóa trùng nhau rất nhiều (nghìn giá trị khóa cho một triệu bản ghi) và đếm số cặp cùng khóa bị đảo thứ tự gốc. Merge sort: 0 cặp đảo — hoàn toàn ổn định. Quicksort: 488.887 cặp đảo — nó xáo tung thứ tự của các phần tử bằng nhau. Khi bạn sắp một bảng theo cột A rồi theo cột B và muốn giữ thứ tự A trong các nhóm B bằng nhau, tính ổn định này là bắt buộc, và quicksort không cho bạn. Thứ hai, không ca xấu: merge sort trên mảng đã sắp hai triệu phần tử chạy 27 mili giây — nhanh như (thực ra nhanh hơn) trên dữ liệu ngẫu nhiên, chứ không sụp thành O(n²) như quicksort pivot dở. Merge sort đổi 25% tốc độ để lấy hai bảo đảm: thứ tự ổn định và không bao giờ có ngày tồi tệ.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: chọn thuật toán sắp xếp theo tính chất bạn cần, không theo một chữ "nhanh" trần trụi. Cần tốc độ thô trên dữ liệu trong bộ nhớ và không quan tâm thứ tự phần tử bằng nhau? Quicksort (có ngẫu nhiên hóa pivot). Cần thứ tự ổn định, hoặc cần bảo đảm không bao giờ O(n²), hoặc đang sắp một danh sách liên kết (nơi merge không cần bộ nhớ phụ và quicksort thì vụng), hoặc sắp dữ liệu lớn hơn RAM phải đọc theo dòng từ đĩa (external sort — merge là nền tảng của nó)? Merge sort. Đây là lý do các thư viện chuẩn thường có hai hàm sắp: một loại ổn định (thường nền merge) và một loại không cam kết ổn định (thường nền quicksort/introsort).
Hệ quả thứ hai, về đo lường: khi tối ưu, tách bạch nguyên nhân bằng phép đo, đừng vá theo trực giác. Nếu tôi tin ngay "malloc là thủ phạm", tôi đã đi tối ưu cấp phát và chỉ vắt ra được 6%, trong khi vấn đề thật — di chuyển dữ liệu — nằm chỗ khác và lớn gấp ba. Cách đúng là dựng hai phiên bản chỉ khác nhau một yếu tố (có/không malloc trong vòng nóng) và đo hiệu số, để mỗi con số quy về đúng một nguyên nhân.
Hệ quả thứ ba là con số mang theo: merge sort cùng O(n log n) với quicksort nhưng chậm hơn 1,25 lần (98 so với 121ms) vì phải chép mọi phần tử qua đệm ở mỗi tầng (di chuyển dữ liệu +23ms), chứ không phải vì malloc (chỉ +6%); đổi lại nó ổn định (0 so với 488887 cặp đảo) và không có ca xấu (mảng đã sắp 27ms). Big-O giống nhau không có nghĩa là hiệu năng giống nhau, và giá trị của một thuật toán không phải lúc nào cũng là tốc độ — đôi khi là những bảo đảm nó cho bạn.
Thử ba mươi giây
Lần tới khi bạn gọi một hàm sắp xếp, hỏi một câu bạn có thể chưa từng hỏi: nó có ổn định không? Với nhiều ngôn ngữ, câu trả lời được ghi rõ trong tài liệu và nó quyết định hành vi thật của bạn — ví dụ khi sắp một danh sách đã sắp theo tên rồi sắp lại theo tuổi, một sort ổn định giữ các người cùng tuổi theo thứ tự tên, một sort không ổn định thì không. Thử nhanh: tạo vài bản ghi có khóa trùng, sắp, và xem thứ tự các bản ghi cùng khóa có giữ nguyên không. Và nếu bạn từng thấy một đoạn code sắp xếp chậm bất ngờ, đừng vội đoán "chắc tại cấp phát" — hãy đo hai phiên bản khác nhau đúng một yếu tố, để đồng hồ chỉ cho bạn thủ phạm thật, thứ mà trực giác rất hay chỉ nhầm.
