Động lực

Merge Sort chia bài toán thành các bài toán con nhỏ hơn, giải từng bài toán rồi kết hợp kết quả. Bước kết hợp đó, gộp hai danh sách đã được sắp xếp, chính là cốt lõi của thuật toán.

Tại sao nên học Merge Sort?

• Nhanh và dễ dự đoán: thuật toán chạy trong thời gian O(n log n) ở trường hợp tốt nhất, trung bình và tệ nhất.
• Ổn định: các phần tử bằng nhau giữ nguyên thứ tự tương đối ban đầu.
• Phù hợp với dữ liệu lớn: thuật toán hoạt động tốt khi dữ liệu không vừa bộ nhớ (sắp xếp ngoài) và với danh sách liên kết.
• Chia để trị: thuật toán giúp bạn hiểu một mô hình được dùng trong nhiều thuật toán nâng cao.