Merge Sort — chia để trị, ổn định, O(n log n)

Ba module tương tác: cây chia & merge, trộn hai mảng bằng two-pointer, và độ sâu đệ quy = log n.

1. Merge Sort Tree — chia (xuống) rồi merge (lên)

Bấm Bước để xem từng thao tác: pha chia tạo cây từ trên xuống, pha merge tô màu hai nửa (xanh = trái, vàng = phải) rồi trộn lên.

Nhập mảng rồi bấm "Dựng cây".

2. Merge hai mảng đã sort — two-pointer

Hai con trỏ (viền vàng) trỏ đầu mỗi mảng. Mỗi bước so sánh, lấy phần tử nhỏ hơn (viền xanh đậm) vào kết quả. ≤ ưu tiên trái → giữ stability.

Nạp hai mảng đã sort rồi bấm "Bước".

3. Độ sâu đệ quy — số tầng = log n, công mỗi tầng = n

Mỗi tầng chia đôi kích thước. Tổng kích thước các mảnh trên một tầng luôn = n → công mỗi tầng O(n). Số tầng = ⌈log₂ n⌉ → tổng O(n log n).

Thử: tăng n gấp đôi — số tầng chỉ +1 (log n), nhưng mỗi tầng vẫn quét đủ n phần tử: tổng công n·log n.