Sắp xếp trộn
Sắp xếp trộn biến một bài toán khó thành nhiều bài toán dễ: hai danh sách đã sắp xếp rất dễ gộp thành một. Chia đôi danh sách cho đến khi mỗi mảnh chỉ còn một giá trị, rồi trộn các mảnh lại với nhau. Đây là thuật toán chia để trị kinh điển, và thời gian của nó là n log n với mọi đầu vào.
Ý tưởng
Trộn là phần dễ. Cho hai danh sách đều đã sắp xếp, so sánh giá trị đầu tiên của chúng và lấy giá trị nhỏ hơn. So sánh hai giá trị đầu tiên mới và lại lấy giá trị nhỏ hơn. Khi một danh sách hết, nối phần còn lại của danh sách kia vào sau. Mỗi bước lấy một giá trị, nên trộn hai danh sách có tổng độ dài m cần nhiều nhất m − 1 phép so sánh. Sắp xếp trộn dùng điều đó để sắp xếp: chia đôi danh sách, sắp xếp từng nửa bằng sắp xếp trộn, rồi trộn hai nửa.
Ví dụ
Lấy 5, 1, 4, 2, 8. Chia thành 5, 1 và 4, 2, 8. Nửa đầu chia thành 5 và 1, trộn lại thành 1, 5. Nửa sau chia thành 4 và 2, 8; 2, 8 được trộn từ 2 và 8, rồi trộn với 4 thành 2, 4, 8. Cuối cùng trộn 1, 5 và 2, 4, 8: 1, rồi 2, rồi 4, rồi 5, và còn lại 8. Tổng cộng 8 phép so sánh, 12 lần ghi và 4 lần trộn.
Vì sao là n log n
Mỗi lần chia làm các mảnh nhỏ đi một nửa, nên sau khoảng log₂ n tầng mỗi mảnh chỉ còn một giá trị. Trên đường đi lên, mỗi tầng trộn xử lý mỗi giá trị một lần, tức là n lần ghi và ít hơn n phép so sánh mỗi tầng. Tổng cộng khoảng n log₂ n. Với 40 giá trị, phép sắp xếp thực hiện 216 lần ghi và nhiều nhất 177 phép so sánh; sắp xếp nổi bọt có thể cần 780 phép so sánh cho cùng danh sách. Thứ tự đầu vào cũng ít ảnh hưởng hơn nhiều so với các thuật toán đó: với 40 giá trị, danh sách đã sắp xếp cần 100 phép so sánh, danh sách đảo ngược cần 116, và danh sách ngẫu nhiên khoảng 160.
Bộ đệm và tính ổn định
Để trộn hai nửa nằm cạnh nhau trong danh sách, cách thông thường là chép chúng ra bộ đệm rồi ghi lại theo thứ tự. Ứng dụng hiển thị bộ đệm đó là hàng cột thứ hai. Nó cần thêm bộ nhớ bằng danh sách, đó là chi phí chính của sắp xếp trộn. Đổi lại, phép sắp xếp ổn định: khi hai giá trị đầu bằng nhau, giá trị từ nửa trái được lấy trước, nên các giá trị bằng nhau giữ nguyên thứ tự. Tính ổn định quan trọng khi sắp xếp bản ghi lần lượt theo từng trường.
Lịch sử và ứng dụng
John von Neumann mô tả sắp xếp trộn vào năm 1945, khiến nó trở thành một trong những thuật toán đầu tiên được viết cho máy tính lưu trữ chương trình. Vì đọc và ghi dữ liệu theo những đoạn dài liên tiếp, nó từng là phương pháp chuẩn để sắp xếp dữ liệu trên băng từ và vẫn được dùng cho các tệp quá lớn so với bộ nhớ. Timsort, được Python và Java (cho đối tượng) sử dụng, là một dạng sắp xếp trộn: trước tiên nó tìm các đoạn đã được sắp xếp sẵn và dùng sắp xếp chèn cho các mảnh ngắn.
Khám phá
Mở ứng dụng và nhấn Bước. Phần được tô bóng của danh sách đang được chia hoặc trộn, và đường nét đứt đánh dấu điểm giữa. Khi bắt đầu trộn, cả hai nửa rơi xuống hàng bộ đệm; hai giá trị đầu được so sánh, và giá trị nhỏ hơn đi lên lại. Theo dõi các bộ đếm: số lần ghi như nhau với mọi danh sách cùng độ dài, còn số phép so sánh thấp nhất với danh sách đã sắp xếp hoặc đảo ngược và cao nhất với danh sách ngẫu nhiên, nhưng không bao giờ vượt quá khoảng n log₂ n.
Câu hỏi thường gặp
Độ phức tạp thời gian của sắp xếp trộn là bao nhiêu?
O(n log n) trong trường hợp tốt nhất, trung bình và xấu nhất. Phiên bản thông thường cần thêm O(n) bộ nhớ cho bộ đệm.
Sắp xếp trộn khác sắp xếp nhanh thế nào?
Cả hai đều chia danh sách và sắp xếp các phần. Sắp xếp trộn chia ở giữa mà không nhìn vào các giá trị và làm việc chính khi trộn; sắp xếp nhanh làm việc chính khi chia, bằng cách di chuyển các giá trị quanh một chốt, và không cần trộn. Sắp xếp nhanh sắp xếp tại chỗ và thường nhanh hơn trong thực tế, nhưng có thể chậm đến n² với đầu vào xấu và không ổn định. Sắp xếp trộn luôn là n log n và ổn định.
Sắp xếp trộn từ dưới lên là gì?
Một phiên bản không dùng đệ quy: trước tiên trộn các giá trị đơn lẻ kề nhau thành từng cặp, rồi các cặp thành nhóm bốn, cứ thế, mỗi vòng gấp đôi độ dài. Nó làm cùng lượng công việc như phiên bản từ trên xuống được minh họa ở đây.
Sắp xếp trộn có ổn định không?
Có, miễn là khi bằng nhau thì lấy giá trị từ nửa trái trước, như ứng dụng này làm.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Thử sắp xếp trộn