Cách hoạt động?

Merge Sort thực hiện ba bước: chia, chinh phục và kết hợp.

Quy trình từng bước:

1. Chia: chia mảng thành hai nửa.
2. Chinh phục: sắp xếp đệ quy từng nửa. Một phần chỉ có một phần tử (hoặc không có phần tử nào) đã được sắp xếp, vì vậy quá trình đệ quy dừng ở đó.
3. Kết hợp: trộn hai nửa đã sắp xếp thành một mảng đã sắp xếp.

Ví dụ với [6, 3, 8, 5]:

• Chia thành [6, 3] và [8, 5]
• Chia tiếp: [6], [3], [8], [5]
• Trộn [6] và [3] thành [3, 6]
• Trộn [8] và [5] thành [5, 8]
• Trộn [3, 6] và [5, 8] thành [3, 5, 6, 8]