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).