Cùng một bài, đọc bằng chữ. Nhanh hơn và tìm lại được bằng Ctrl+F.
Tám số, bốn tầng
- Chia8 số thành hai nửa, mỗi nửa 4 số
- Chia tiếpMỗi nửa lại thành hai phần 2 số
- Chạm đáyCòn 1 số thì tự nó đã đúng thứ tự
- Trộn ngượcGhép đôi một lên, mỗi lần trộn hai dãy
Trộn hai dãy đã đúng thứ tự
Nhìn phần tử đầu của hai dãy, lấy số nhỏ hơn ra trước, rồi lặp lại. Vì hai dãy đã đúng thứ tự sẵn, mỗi bước chỉ cần so một cặp. Đó là toàn bộ bước trộn.
Cái giá phải trả
Bước này cần một mảng phụ cỡ n
n log n đến từ đâu
Mỗi tầng xử lý tổng cộng n phần tử. Số tầng là số lần chia đôi được, tức log n. Nhân hai thứ đó ra n log n. Đếm tầng là đủ, không cần công thức truy hồi.
Merge sort được gì, mất gì
Ưu điểm
Luôn n log n, kể cả trường hợp xấu nhất
Ổn định, hợp khi sắp theo nhiều khoá
Chạy được trên dữ liệu lớn hơn RAM
Nhược điểm
Cần mảng phụ cỡ n, không sắp xếp tại chỗ
Mảng cỡ vừa thì chậm hơn quick sort
Đệ quy log n tầng, code khó đọc hơn
Bài sau: quick sort
Nhanh hơn merge sort trên thực tế, nhưng có một trường hợp làm nó sập về n².
