Merge sort là một thuật toán sắp xếp theo divide-and-conquer, ổn định (stable), chạy với thời gian O(n log n) được đảm bảo. Nó chia mảng làm đôi, sắp xếp đệ quy mỗi nửa, rồi trộn hai nửa đã sắp xếp lại.
Ý tưởng
Một phần tử đơn lẻ thì đã được sắp xếp (base case). Việc trộn hai danh sách đã sắp xếp là tuyến tính, và chúng ta thực hiện log n tầng trộn.
