log n trong merge sort chỉ là số tầng của cây chia đôi, đếm được bằng mắt

Cây chia đôi trên tám số

1. Tầng 05 2 8 1 9 3 7 4 — một mảng tám phần tử
2. Tầng 15 2 8 1 và 9 3 7 4 — hai mảng bốn
3. Tầng 25 2 · 8 1 · 9 3 · 7 4 — bốn mảng hai
4. Tầng 3Tám mảng một phần tử. Ba tầng chia, vì chia đôi tám ba lần

Trộn hai mảng đã đúng thứ tự

Đặt một con trỏ ở đầu mỗi mảng, mỗi bước lấy phần tử nhỏ hơn rồi đẩy con trỏ đó lên một. Trộn 2 5 với 1 8 ra 1 2 5 8. Mỗi phần tử chỉ được nhìn đúng một lần.

n log n nằm ở đâu

Mỗi tầng trộn lại đúng n phần tử, dù tầng đó chia thành bao nhiêu mảng nhỏ. Có log n tầng. Nhân hai thứ đó ra n log n, không cần công thức truy hồi nào.

Không có trường hợp xấu nhất

Số tầng chỉ phụ thuộc số phần tử, không phụ thuộc dữ liệu. Mảng đã đúng thứ tự hay đảo ngược đều tốn đúng ngần đó. Quick sort không có tính chất này.

Merge sort: được gì, mất gì

Lưu lại để chạy tay sau

Loạt bài thuật toán sắp xếp cho dev Việt Nam.