Sắp xếp trộn
Sắp xếp trộn, và một thuật toán gần như không thèm nhìn dữ liệu
Ba thuật toán bậc hai đổi hoá đơn tới 8 lần khi bạn đổi dữ liệu vào. Sắp xếp trộn thì không: mọi mảng 16 phần tử đều tốn từ 32 tới 49 phép so sánh, và bốn con số khác thì đứng yên tuyệt đối.
Ở bài ba thuật toán sắp xếp bậc hai bạn đã thấy nhãn O(n²) giấu đi cái gì: trên mảng 16 phần tử, sắp xếp chèn tốn 15 phép so sánh khi mảng đã sắp và 120 phép khi mảng đảo ngược, tức chênh nhau 8 lần trong cùng một nhãn. Bài này đổi câu hỏi: nếu chấp nhận chia mảng ra rồi ghép lại, chi phí sẽ thành cái gì.
Ý tưởng ngắn tới mức nghe như ăn gian. Muốn sắp một mảng, hãy chia đôi, sắp từng nửa, rồi trộn hai nửa đã sắp lại với nhau. Trộn hai dãy đã sắp là việc dễ: cứ nhìn hai đầu, lấy cái nhỏ hơn, lặp lại. Còn "sắp từng nửa" thì gọi lại chính nó, cho tới khi đoạn chỉ còn một phần tử, và một phần tử thì đã sắp sẵn rồi. Đây là đệ quy ở dạng thuần túy nhất: hàm tự gọi mình trên bài toán nhỏ hơn, và có một ca đáy để dừng.
Sim dưới đây chạy đúng thuật toán đó, vẽ cả cây lời gọi, đi từng lần trộn, và đếm bốn thứ: số phép so sánh, số phép chép, độ sâu đệ quy, và số ô nhớ phụ. Cách đếm phép so sánh và phép dời chỗ giữ y hệt bài trước, nên bạn đặt hai trang cạnh nhau và so trực tiếp được.
1 · Mảng vào ✎ sửa được
2 · Hoá đơn của mảng này
| đại lượng | đoán trước bằng công thức | công thức | chạy thật | khớp |
|---|---|---|---|---|
| phép chép | 2·W(n) = 2·64 | 128 | 128 | ✓ |
| số lần trộn | n − 1 = 16 − 1 | 15 | 15 | ✓ |
| độ sâu đệ quy | ⌈log₂ n⌉ + 1 cho n ≥ 1 | 5 | 5 | ✓ |
| ô mà các lần trộn đi qua | W(n) = W(⌊n/2⌋) + W(⌈n/2⌉) + n | 64 | 64 | ✓ |
| so sánh, cận dưới | B(n), rẻ nhất mà mọi mảng 16 phần tử có thể đạt | 32 | 46 | ✓ ≥ |
| so sánh, cận trên | C(n) = n⌈log₂ n⌉ − 2^⌈log₂ n⌉ + 1 = 49 | 49 | 46 | ✓ ≤ |
- So sánh: mỗi lần hai phần tử của mảng được đem ra so với nhau. Đúng định nghĩa của bài trước, nên hai trang so được trực tiếp với nhau.
- Dời chỗ: mỗi lần một phần tử nằm sang ô khác ô nó đang giữ trước lần trộn đó. Cũng đúng định nghĩa bài trước, và cũng vì thế mảng đã sắp cho 0.
- Phép chép là con số bài trước không có. Mỗi lần trộn, cả đoạn được chép vào vùng đệm rồi chép ngược lại, kể cả những phần tử về đúng ô cũ. Nên phép chép luôn bằng
2·W(n)và không hề nhìn dữ liệu. Chép mà không dời chỗ vẫn là công thật: vẫn phải đọc, vẫn phải ghi. - Đổi chỗ bằng 0 ở đây, và không phải vì ai đó quên đếm: sắp xếp trộn không bao giờ hoán vị hai ô cho nhau, nó chỉ chép.
3 · Năm kiểu dữ liệu, cùng 16 phần tử
| kiểu dữ liệu | cặp bị đảo | so sánh | phép chép | dời chỗ | mảng vào |
|---|---|---|---|---|---|
| đã sắp | 0 | 32 | 128 | 0 | 12345678910111213141516 |
| đảo ngược | 120 | 32 | 128 | 64 | 16151413121110987654321 |
| ▸ ngẫu nhiên có hạt giống | 53 | 46 | 128 | 49 | 41253111413210768915161 |
| gần như đã sắp | 3 | 34 | 128 | 5 | 12345678910141112131516 |
| ép trộn tốn nhất | 76 | 49 | 128 | 64 | 16812414610215711313591 |
4 · Chia xuống, rồi trộn ngược lên
| lần | mức | trái | phải | ra | so sánh | tối đa | chép thẳng không so sánh |
|---|---|---|---|---|---|---|---|
| 1 | 4 | 4 | 12 | 412 | 1 | 1 | 1 phần tử cuối, từ nhánh phải |
| 2 | 4 | 5 | 3 | 35 | 1 | 1 | 1 phần tử cuối, từ nhánh trái |
| 3 | 3 | 412 | 35 | 34512 | 3 | 3 | 1 phần tử cuối, từ nhánh trái |
| 4 | 4 | 11 | 14 | 1114 | 1 | 1 | 1 phần tử cuối, từ nhánh phải |
| 5 | 4 | 13 | 2 | 213 | 1 | 1 | 1 phần tử cuối, từ nhánh trái |
| 6 | 3 | 1114 | 213 | 2111314 | 3 | 3 | 1 phần tử cuối, từ nhánh trái |
| 7 | 2 | 34512 | 2111314 | 234511121314 | 6 | 7 | 2 phần tử cuối, từ nhánh phải |
| 8 | 4 | 10 | 7 | 710 | 1 | 1 | 1 phần tử cuối, từ nhánh trái |
| 9 | 4 | 6 | 8 | 68 | 1 | 1 | 1 phần tử cuối, từ nhánh phải |
| 10 | 3 | 710 | 68 | 67810 | 3 | 3 | 1 phần tử cuối, từ nhánh trái |
| 11 | 4 | 9 | 15 | 915 | 1 | 1 | 1 phần tử cuối, từ nhánh phải |
| 12 | 4 | 16 | 1 | 116 | 1 | 1 | 1 phần tử cuối, từ nhánh trái |
| 13 | 3 | 915 | 116 | 191516 | 3 | 3 | 1 phần tử cuối, từ nhánh phải |
| 14 | 2 | 67810 | 191516 | 16789101516 | 6 | 7 | 2 phần tử cuối, từ nhánh phải |
| 15 | 1 | 234511121314 | 16789101516 | 12345678910111213141516 | 14 | 15 | 2 phần tử cuối, từ nhánh phải |
độ dài − 1. Cộng cả cột lại được 49, đúng bằng cận trên ở bảng 2. Lần chạy này tiêu 46, tức tiết kiệm được 3 phép nhờ những đoạn chép thẳng, và tổng số phần tử chép thẳng là 18.5 · Không thuật toán so sánh nào rẻ hơn được
| n | log₂(n!) | chặn dưới, làm tròn lên | trộn, ca xấu nhất | dư ra | tỉ lệ |
|---|---|---|---|---|---|
| 2 | 1,00 | 1 | 1 | 0 | 1,000 |
| 4 | 4,58 | 5 | 5 | 0 | 1,091 |
| 8 | 15,30 | 16 | 17 | 1 | 1,111 |
| ▸ 16 | 44,25 | 45 | 49 | 4 | 1,107 |
| 32 | 117,66 | 118 | 129 | 11 | 1,096 |
n!. Muốn phân biệt hết thì phải hỏi ít nhất log₂(n!) câu trong ca xấu nhất. Đó là chặn dưới cho mọi thuật toán sắp xếp dựa trên so sánh, không riêng gì sắp xếp trộn. Cột dư ra cho thấy sắp xếp trộn nằm ngay sát cái sàn đó. Chú ý: chặn dưới nói về ca xấu nhất, nên đừng đem nó so với con số của một mảng dễ: mảng đã sắp 16 phần tử chỉ tốn 32 phép, và nó không hề mâu thuẫn với chặn dưới 45.6 · Một dấu bằng quyết định tính ổn định ✎ sửa được
| chạy cái gì | kết quả, đọc từ trái sang | so sánh | giữ nguyên thứ tự cũ của khoá bằng nhau |
|---|---|---|---|
| đầu vào | 3A1B3C2D1E | — | chưa sắp gì cả |
| ▸ bằng nhau thì lấy bên trái | 1B1E2D3A3C | 8 | ✓ có, thứ tự cũ còn nguyên |
| bằng nhau thì lấy bên phải | 1E1B2D3C3A | 8 | ✗ không: cùng khoá 1, B vào trước E mà lại ra sau |
- Nó đếm phép tính, nó không đo thời gian chạy. Sắp xếp trộn còn phải cấp phát vùng đệm và đi lại giữa hai vùng nhớ, và hai thứ đó không hiện ra trong bất kỳ con số nào ở đây.
- Cách đếm phép chép là một quy ước: bản cài đặt này chép cả đoạn vào vùng đệm rồi chép ngược lại, nên mỗi phần tử bị ghi 2 lần mỗi mức. Có bản cài đặt luân phiên hai mảng và chỉ ghi 1 lần mỗi mức. Đổi quy ước thì cột đó chia đôi, còn cột so sánh giữ nguyên.
- Bản cài đặt ở đây là trộn từ trên xuống, chia đôi bằng
(lo + hi) >> 1. Bản từ dưới lên ghép các đoạn dài 1, 2, 4, ... cho ra số phép so sánh hơi khác ở n không phải luỹ thừa của 2. - Ca xấu nhất ở đây là ca xấu nhất đã dựng được, không phải đoán: kiểu ép trộn tốn nhất là một mảng thật, và số phép nó tiêu đúng bằng công thức chặn trên ở bảng 2.
- Dãy ngẫu nhiên sinh bằng bộ sinh giả ngẫu nhiên viết trong engine, không dùng đồng hồ và không dùng
Math.random. Cùng hạt giống thì luôn cùng dãy, trên máy chủ cũng như trên trình duyệt.
Trạng thái mở bài đang nói gì
Sim khởi động ở kiểu ngẫu nhiên có hạt giống: 16 phần tử, hạt giống 2026, ra mảng 4 12 5 3 11 14 13 2 10 7 6 8 9 15 16 1. Mảng này có 53 cặp bị đảo trên tối đa 120 cặp mà 16 phần tử có thể chứa, tức khá lộn xộn. Hoá đơn như sau.
- 46 phép so sánh. Rẻ nhất mà một mảng 16 phần tử có thể đạt là 32, đắt nhất là 49. Mảng này nằm ở khoảng 82% quãng đường từ đầu rẻ tới đầu đắt, nghĩa là dữ liệu trộn lẫn thì gần như luôn sát ca xấu nhất.
- 128 phép chép. Con số này không phụ thuộc dữ liệu một chút nào, nó bằng đúng
2 · W(16)vớiW(16) = 64là tổng số ô mà các lần trộn phải đi qua. - 49 phép dời chỗ. Đây mới là con số đọc dữ liệu, và nó khác hẳn phép chép: chép là ghi một giá trị vào một ô, còn dời chỗ chỉ tính khi giá trị đó sang ô khác.
- 15 lần trộn, 31 lời gọi hàm, sâu 5 mức. Cây có
2n − 1 = 31nút, trong đó 16 nút lá là các đoạn một phần tử và 15 nút trong là các lời gọi phải trộn. - 16 ô nhớ phụ. Vùng đệm lúc đông nhất giữ trọn 16 phần tử, đúng bằng
n. Ba thuật toán bậc hai ở bài trước cần 0 ô.
Trong 46 phép so sánh đó, ca xấu nhất là 49, nên các đoạn chép thẳng đã tiết kiệm được 3 phép. Tổng cộng có 18 phần tử được chép sang mà không phải so với ai. Chỗ này là chìa khoá của cả bài, nên nó có một mục riêng ở dưới.
Chia xuống, trộn lên, và bốn con số không đọc dữ liệu
Mục 4 của sim vẽ cây lời gọi thành từng mức. Mức 1 là cả mảng, mức 2 là hai nửa, cứ thế cho tới mức cuối toàn đoạn một phần tử. Với 16 phần tử thì có 5 mức, vì mỗi mức chia đôi kích thước và 16 = 2⁴.
Bốn đại lượng dưới đây tính thẳng ra từ n, chưa cần biết mảng chứa gì:
- Số ô các lần trộn đi qua:
W(n) = W(⌊n/2⌋) + W(⌈n/2⌉) + n, vớiW(0) = W(1) = 0. Khinlà luỹ thừa của 2 thì mỗi mức trộn phủ kín mảng đúng một lần, nên mỗi mức gópnô vàW(n) = n·log₂ n: vớin = 16là4 · 16 = 64. Kích thước khác thì mức trộn dưới cùng chỉ phủ được một phần mảng, nênWnhỏ hơnn⌈log₂ n⌉chứ không bằng. Vớin = 13, bốn mức trộn góp lần lượt 13, 13, 13 và 10 ô, tổngW = 49chứ không phải 52. - Số phép chép:
2 · W(n). Bản cài đặt này chép cả đoạn vào vùng đệm rồi chép ngược lại, nên mỗi ô bị ghi hai lần mỗi lần trộn. Vớin = 16là 128. - Số lần trộn:
n − 1. Cây cónlá và mỗi lần trộn ứng với một nút trong, mà cây nhị phânnlá có đúngn − 1nút trong. - Độ sâu đệ quy:
⌈log₂ n⌉ + 1mức, vớin ≥ 1. Mảng rỗng thì hàm không được gọi lần nào nên độ sâu bằng 0.
Cổng kiểm số chạy lại cả bốn công thức trên 924 cấu hình, và đối chiếu với một lần chạy thật lẫn với một phép duyệt cây viết theo lối lặp thay vì đệ quy. Không cấu hình nào lệch. Nó cũng khoá một chuyện dễ nói ẩu: khi bạn đổi kiểu dữ liệu, cả bốn con số này không nhúc nhích ở bất kỳ kích thước nào từ 2 tới 32.
Một chỗ đáng chú ý cho người mới đọc đệ quy: kích thước không phải luỹ thừa của 2 vẫn chạy đúng. Đặt số phần tử về 13, 13 chia thành 6 và 7, rồi 7 chia thành 3 và 4. Cây lệch một bên nhưng không hỏng. Với 13 phần tử: 12 lần trộn, 98 phép chép, sâu 5 mức.
Điểm chính: đổi dữ liệu, con số gần như đứng yên
Đây là chỗ bài này khác hẳn bài trước, và mục 3 của sim tồn tại chỉ để cho thấy nó. Bảng đó chạy cả năm kiểu dữ liệu trên cùng một kích thước, nên bạn không phải bấm qua lại rồi nhớ số.
Với 16 phần tử, hạt giống 2026:
| kiểu dữ liệu | so sánh | phép chép | dời chỗ |
|---|---|---|---|
| đã sắp | 32 | 128 | 0 |
| đảo ngược | 32 | 128 | 64 |
| ngẫu nhiên | 46 | 128 | 49 |
| gần như đã sắp, 3 cặp đảo | 34 | 128 | 5 |
| ép trộn tốn nhất | 49 | 128 | 64 |
Cột phép chép ra đúng một con số cho cả năm kiểu. Cột so sánh chạy từ 32 tới 49, tức kiểu đắt nhất tốn 1,53 lần kiểu rẻ nhất. Đem so với bài trước trên cùng 16 phần tử: sắp xếp chèn chạy từ 15 tới 120, tức 8 lần. Cả hai con số 15 và 120 đều được cổng kiểm số dựng lại bằng một bản sắp xếp chèn viết riêng trong tệp kiểm, chứ không chép từ trang cũ.
Con số 1,53 lần là ở n = 16. Quét toàn dải kích thước mà sim cho phép, chỗ khoảng cách mở rộng nhất là n = 21, và ở đó tỉ lệ là 1,76 lần. Không kích thước nào trong dải vượt quá 1,77. Lý do có chặn: mỗi lần trộn đoạn dài L tốn nhiều nhất L − 1 phép và ít nhất ⌊L/2⌋ phép, nên cộng cả cây lại thì hai đầu chỉ chênh nhau chưa tới 2 lần.
Chuyện gây bất ngờ nhất trong bảng là dòng đảo ngược: 32 phép so sánh, đúng bằng mảng đã sắp. Ở bài trước, đảo ngược là ca xấu nhất của sắp xếp chèn. Ở đây nó là ca rẻ nhất, ngang với mảng đã sắp. Lý do nằm ở chỗ trộn: sau khi hai nửa đã được sắp, nửa trái của mảng đảo ngược chứa toàn giá trị lớn, nên nhánh phải hết trước và phần đuôi bên trái được chép thẳng. Mảng đã sắp thì ngược lại, nhánh trái hết trước. Cổng kiểm số khoá đúng chiều đó: trên mảng đã sắp, mọi đoạn đuôi đến từ nhánh phải; trên mảng đảo ngược, mọi đoạn đuôi đến từ nhánh trái.
Hai kiểu ấy giống nhau ở cột so sánh nhưng khác hẳn ở cột dời chỗ: 0 với 64. Mảng đã sắp không có phần tử nào phải đi đâu, còn mảng đảo ngược thì mọi ô của mọi lần trộn đều đổi chỗ, và 64 đúng bằng W(16). Đây là lý do phải đếm hai cột chứ không phải một, y như bài trước.
Nhưng "gần như" không phải "hoàn toàn"
Ba chỗ dưới đây là chỗ câu "sắp xếp trộn không quan tâm dữ liệu" sẽ sai nếu nói tròn trịa.
Thứ nhất, mảng dễ vẫn rẻ hơn ca xấu nhất, và chênh lệch đo được. Với 16 phần tử, mảng đã sắp tốn 32 phép còn ca xấu nhất tốn 49, chênh 17 phép. Với 32 phần tử là 80 với 129, chênh 49 phép. Nguồn của khoản tiết kiệm đó nhìn thấy được ở mục 4: trên mảng đã sắp, 32 phần tử được chép thẳng không so sánh lần nào, còn trên mảng ép trộn tốn nhất chỉ có 15, tức đúng một phần tử cho mỗi lần trộn, mức tối thiểu tuyệt đối.
Thứ hai, ở kích thước lẻ thì "đã sắp" và "đảo ngược" thôi bằng nhau. Đặt số phần tử về 13: mảng đã sắp tốn 22 phép, mảng đảo ngược tốn 27, chênh 5 phép. Lý do là phép chia đôi (lo + hi) >> 1 cho nửa trái ngắn hơn khi độ dài lẻ, mà một lần trộn tốn số phép bằng độ dài trừ đi phần đuôi chép thẳng, nên nhánh nào hết trước sẽ quyết định. Mảng đã sắp làm nhánh ngắn hết trước, tức rẻ hơn. Ở n = 16 mọi lần chia đều đều nên hai kiểu bằng nhau, và nếu chỉ thử ở luỹ thừa của 2 thì bạn sẽ kết luận sai.
Thứ ba, sắp xếp trộn có thích ứng, nhưng không đơn điệu. Chuyển sang kiểu gần như đã sắp rồi kéo núm số cặp bị đảo từ 0 lên hết cỡ, với 16 phần tử và hạt giống 2026:
| cặp bị đảo | trộn | chèn (bài trước) |
|---|---|---|
| 0 | 32 | 15 |
| 3 | 34 | 18 |
| 30 | 44 | 45 |
| 60 | 46 | 75 |
| 90 | 40 | 104 |
| 120 | 32 | 120 |
Cột chèn bò thẳng lên rồi đụng trần. Cột trộn thì lên tới khoảng 46 ở giữa rồi tụt trở lại 32 ở đầu kia, vì mảng có đủ 120 cặp bị đảo chính là mảng đảo ngược, mà đảo ngược lại là ca rẻ. Trên toàn bộ 120 bước kéo núm, con số của sắp xếp trộn đi lên 19 lần và đi xuống 20 lần. Nói "càng lộn xộn càng đắt" là đúng với sắp xếp chèn và sai với sắp xếp trộn.
Chặn dưới: không thuật toán so sánh nào rẻ hơn được
Câu hỏi tự nhiên sau khi thấy 49 phép cho 16 phần tử: liệu có thuật toán nào rẻ hơn hẳn không.
Có một câu trả lời chặn cứng. Một thuật toán chỉ được phép hỏi a có nhỏ hơn b không thì mỗi câu hỏi có 2 khả năng trả lời, nên sau k câu nó phân biệt được nhiều nhất 2ᵏ trường hợp. Mà số thứ tự có thể của n phần tử là n!. Muốn phân biệt hết thì phải có 2ᵏ ≥ n!, tức k ≥ log₂(n!). Đây là chặn dưới cho mọi thuật toán sắp xếp dựa trên so sánh, không riêng gì sắp xếp trộn.
Mục 5 của sim tính con số đó rồi đặt cạnh ca xấu nhất của sắp xếp trộn:
| n | log₂(n!) | chặn dưới, làm tròn lên | trộn, ca xấu nhất | dư ra |
|---|---|---|---|---|
| 2 | 1,0000 | 1 | 1 | 0 |
| 16 | 44,2501 | 45 | 49 | 4 |
| 32 | 117,6633 | 118 | 129 | 11 |
Ở n = 16, sắp xếp trộn tiêu nhiều hơn cái sàn lý thuyết đúng 4 phép so sánh, tức tỉ lệ 1,1073. Ở n = 32 là 11 phép, tỉ lệ 1,0963. Nói cách khác, thuật toán này đã gần tối ưu tới mức chỗ để cải thiện còn lại chỉ khoảng một phần mười.
Hai chỗ dễ hiểu sai, và cả hai đều đã đo:
Chặn dưới nói về ca xấu nhất, không nói về từng mảng. Mảng đã sắp 16 phần tử chỉ tốn 32 phép, tức dưới cái sàn 45. Không hề mâu thuẫn: lập luận trên nói cây quyết định phải cao ít nhất log₂(n!), chứ không nói mọi nhánh của nó đều dài như vậy. Một đầu vào may mắn đi theo nhánh ngắn.
Đừng tính n! rồi mới lấy logarit. Kiểu số thực của máy hết chỗ ở 171!: cổng kiểm số đo được 170! vẫn là một số hữu hạn còn 171! trả về vô cùng, nên đường đi qua giai thừa chết đúng ở đó. Cộng logarit thì không bao giờ tràn, và nó vẫn cho log₂(171!) = 1026,7873. Bài bậc tăng nói về việc bỏ hằng số, còn đây là một chuyện khác hẳn: cùng một giá trị toán học, hai cách tính, một cách hỏng.
Tính ổn định nằm trong đúng một dấu bằng
Một thuật toán sắp xếp gọi là ổn định khi hai phần tử có khoá bằng nhau vẫn giữ nguyên thứ tự cũ sau khi sắp. Bài trước cho thấy sắp xếp chọn không có bảo đảm đó. Sắp xếp trộn thì có, và mục 6 của sim chỉ ra chỗ nó nằm.
Trong vòng trộn, khi hai đầu bằng nhau thì phải chọn lấy bên nào. Điều kiện trái ≤ phải lấy bên trái, mà bên trái chính là nửa vào trước, nên thứ tự cũ được giữ. Đổi thành trái < phải thì bằng nhau sẽ nhường bên phải, và thứ tự cũ vỡ.
Bấm nút để đổi luật, trên danh sách 3A 1B 3C 2D 1E của bài trước:
- lấy bên trái: ra
1B 1E 2D 3A 3C, B trước E và A trước C, đúng như lúc vào; - lấy bên phải: ra
1E 1B 2D 3C 3A, cả hai cặp đều bị đảo.
Điều đáng nói là số phép so sánh của hai luật bằng nhau, cùng 8 phép. Chỉ số phép dời chỗ nhích từ 10 lên 12. Nghĩa là tính ổn định ở đây không phải thứ mua bằng công sức, nó là hệ quả của một lựa chọn viết mã, và người viết chỉ cần biết mình đang chọn gì. Cổng kiểm số khoá cả hai chiều trên cả bốn danh sách: luật trái luôn ổn định, luật phải luôn không, và chi phí so sánh luôn bằng nhau.
Danh sách ngắn nhất để thấy chuyện đó là 5A 5B: một lần trộn, một phép so sánh. Luật trái ra 5A 5B và không dời chỗ gì; luật phải ra 5B 5A và dời 2 ô. Nhỏ hơn nữa thì không còn gì để hỏi.
Có một chi tiết nhỏ đáng nhớ đúng chiều. Ở bài trước, danh sách 2A 1B 2C là ca mà sắp xếp chọn tình cờ không phá. Ở đây luật phải phá nó. "Không bảo đảm" nghĩa là có lúc đúng có lúc sai, và một lần đúng không chứng minh được gì.
Cái giá: n ô nhớ phụ
Cho tới giờ sắp xếp trộn thắng gần như mọi mặt. Chỗ nó thua nằm ở cột cuối của mục 1.
Vùng đệm lúc đông nhất giữ đúng n ô, vì lần trộn cuối cùng phải chép cả mảng. Cổng kiểm số đo con số này ở mọi kiểu dữ liệu và mọi kích thước từ 2 tới 32, và nó luôn bằng n. Ba thuật toán bậc hai ở bài trước cần 0 ô: chúng đổi chỗ ngay trong mảng. Ngoài vùng đệm còn ngăn xếp lời gọi, sâu bằng độ sâu đệ quy, tức 6 khung với 32 phần tử, và phần này tăng theo logarit nên nó không phải chỗ đáng lo.
n ô nghe không nhiều, nhưng nếu mảng là 8 GB dữ liệu thì bạn cần thêm 8 GB. Đó chính là lý do người ta vẫn dùng sắp xếp nhanh ở nhiều chỗ: cùng bậc n log n ở ca trung bình, mà sắp xếp tại chỗ. Đổi lại, sắp xếp nhanh có ca xấu nhất O(n²) và không ổn định. Không có bữa trưa miễn phí, chỉ có bảng đánh đổi, và bảng đó chỉ đọc được khi bạn chịu đếm từng cột chứ không gộp tất cả vào một chữ O.
Vài điểm nhỏ nhưng hay bị bỏ qua:
- Cách đếm phép chép là một quy ước. Bản cài đặt ở đây chép cả đoạn vào vùng đệm rồi chép ngược lại, nên mỗi phần tử bị ghi 2 lần mỗi mức. Có bản luân phiên hai mảng và chỉ ghi 1 lần mỗi mức. Đổi quy ước thì cột đó chia đôi, còn cột so sánh giữ nguyên.
- Đây là bản trộn từ trên xuống. Bản từ dưới lên ghép các đoạn dài 1, 2, 4 và cứ thế, cho ra số phép so sánh hơi khác khi
nkhông phải luỹ thừa của 2. - Ca xấu nhất trong sim là ca dựng được, không phải ca đoán. Kiểu ép trộn tốn nhất là một mảng thật, dựng bằng cách chạy ngược phép trộn, và số phép nó tiêu đúng bằng công thức
n⌈log₂ n⌉ − 2^⌈log₂ n⌉ + 1. - Mảng rỗng và mảng một phần tử cho 0 phép so sánh, 0 phép chép và 0 ô nhớ phụ, và không lỗi. Hai ca chỉ khác nhau ở một chỗ: mảng rỗng không gọi hàm lần nào nên độ sâu 0, mảng một phần tử gọi đúng một lần rồi trả về nên độ sâu 1.
- Sim đếm phép tính, không đo thời gian. Sắp xếp trộn còn phải cấp phát vùng đệm và đi lại giữa hai vùng nhớ, và không con số nào ở đây nói về hai thứ đó.
Chia đôi tới khi còn một phần tử rồi trộn ngược lên: có ⌈log₂ n⌉ mức trộn và mỗi mức phủ nhiều nhất là cả mảng một lần, nên chi phí thành n log n thay vì n². Cái đáng nhớ hơn con số là tính ít phụ thuộc dữ liệu: với 16 phần tử, số phép chép luôn là 128, số lần trộn luôn là 15, độ sâu luôn là 5, còn số phép so sánh bị kẹp trong khoảng 32 tới 49, tức chênh 1,53 lần, trong khi sắp xếp chèn ở cùng kích thước chênh 8 lần. Nhưng "gần như" không phải "hoàn toàn": mảng đã sắp rẻ hơn ca xấu nhất 17 phép ở n = 16, ở kích thước lẻ thì mảng đã sắp và mảng đảo ngược không còn bằng nhau, và chi phí không đơn điệu theo số cặp bị đảo. Ca xấu nhất 49 phép nằm chỉ 4 phép trên chặn dưới log₂(16!) = 44,25 áp cho mọi thuật toán dựa trên so sánh, mà chặn đó nói về ca xấu nhất chứ không nói về từng mảng. Tính ổn định nằm gọn trong một dấu bằng của điều kiện trộn và không tốn thêm phép so sánh nào. Giá phải trả là n ô nhớ phụ, và đó là lý do sắp xếp tại chỗ vẫn còn chỗ đứng.
- 1Một mảng 16 phần tử đã sắp sẵn đúng thứ tự. Sắp xếp trộn tốn bao nhiêu phép chép, và vì sao?
- 2log₂(16!) bằng khoảng 44,25 và sắp xếp trộn tiêu 49 phép ở ca xấu nhất. Nhưng trên mảng 16 phần tử đã sắp nó chỉ tiêu 32 phép, tức dưới 44,25. Chuyện gì đang xảy ra?
- 3Bạn cần sắp một danh sách 8 GB bản ghi, đã sắp sẵn theo ngày, nay sắp lại theo tên, và các dòng trùng tên phải giữ nguyên thứ tự ngày. Máy còn trống 2 GB. Điều gì đáng lo nhất khi chọn sắp xếp trộn?