Các kỹ thuật sort — Merge Sort

Trộn hai dãy đã sắp xếp thành một dãy sắp xếp chỉ tốn O(n) — đó là "viên gạch" duy nhất mà Merge Sort cần, lặp lại nó theo kiểu chia để trị là xong.

Bài toán

Sắp xếp một mảng số nguyên tăng dần, đảm bảo O(n log n) trong mọi trường hợp (khác Quick Sort).

Ý tưởng của Merge Sort

Nếu một mảng chỉ có 1 phần tử, nó đã "sắp xếp xong". Chia mảng làm đôi, đệ quy sắp xếp từng nửa, rồi trộn (merge) hai nửa đã sắp xếp lại thành một mảng sắp xếp duy nhất: dùng hai con trỏ, mỗi bước lấy phần tử nhỏ hơn giữa hai đầu, đẩy vào mảng tạm, cho đến khi hết cả hai nửa.

Độ phức tạp

Vì luôn ổn định O(n log n) và ổn định (stable — giữ nguyên thứ tự tương đối của các phần tử bằng nhau), Merge Sort là lựa chọn khi cần độ phức tạp đảm bảo hoặc khi cần tính ổn định (ví dụ sắp xếp học sinh theo điểm nhưng vẫn giữ thứ tự theo tên ban đầu).

Ví dụ chạy tay

Mảng [6, 2, 9, 4]:

1. Chia đôi: [6, 2] và [9, 4].
2. Chia tiếp: [6], [2], [9], [4] — mỗi mảng 1 phần tử, coi như đã sắp xếp.
3. Trộn [6] và [2] → [2, 6]. Trộn [9] và [4] → [4, 9].
4. Trộn [2, 6] và [4, 9]: so 2&4→lấy 2, so 6&4→lấy 4, so 6&9→lấy 6, còn lại lấy 9 → [2, 4, 6, 9].

Ứng dụng / dạng bài hay gặp

• Đếm số cặp nghịch thế (inversion count) trong mảng: chỉ cần đếm thêm trong bước trộn, tận dụng luôn Merge Sort có sẵn — độ phức tạp O(n log n) thay vì O(n²) nếu đếm trực tiếp.
• Sắp xếp danh sách liên kết (linked list): Merge Sort tự nhiên hơn Quick Sort vì không cần truy cập ngẫu nhiên theo chỉ số.