下面給出一份“一句話就能落地”的導讀：
Learned Sort 2.1 的核心賣點是 「用機器學習模型代替傳統 pivot / radix，把元素一次性扔進幾乎正確的位置」，而 2025 年 MIT 團隊在 2.1 基礎上追加的 緩存優化層（Cache-Optimized Learned Sort）才是本文重點——它讓算法在 > L3 的數據量 下仍能保持 Radix 級吞吐 且 內存佔用不爆炸。
1 緩存痛點（MIT 實驗原話）
當數組 > L3（≈8 MB）時，Learned Sort 1.x 的隨機桶寫導致 每 7 次寫就 1 次 LLC-miss，吞吐直接腰斬。
2 MIT 2025 緩存方案（已開源）
| 優化點 | 一句話説明 | 實測收益 |
|---|---|---|
| Blocked Bucketing | 把 n 個桶拆成 n/CACHE_BLK 輪，每輪只寫 ≤ L2/2 字節 | LLC-miss ↓ 40 % |
| Software Prefetch | 寫桶前 _mm_prefetch(addr, _MM_HINT_T0) 提前拉線 |
寫延遲隱藏 25 % |
| Index-Buffer in L1 | 用 64×64 B 小數組存 待寫下標，無分支批量交換 | 分支 miss ↓ 90 % |
| Overflow Batch | 溢出桶也按 CACHE_BLK 批量處理，避免隨機跳轉 | 尾部歸併時間 ↓ 30 % |
3 關鍵代碼片段（MIT 官方偽碼 → C++17）
constexpr size_t L2_SIZE = 256 * 1024;
constexpr size_t CACHE_BLK = L2_SIZE / 2 / sizeof(Key); // 32 k key
void learnedSortCached(Key* a, size_t n, CDFModel& model) {
alignas(64) static thread_local std::array<uint32_t, 64> idxBuf;
for (size_t round = 0; round < n; round += CACHE_BLK) {
size_t end = std::min(round + CACHE_BLK, n);
// 1. 預取 + 無分支填充 idxBuf
for (size_t i = round; i < end; ++i) {
_mm_prefetch(a + i + 64, _MM_HINT_T0);
uint32_t bucket = model.predict(a[i]) * BUCKETS;
idxBuf[consumed++] = bucket;
}
// 2. 按塊寫桶（L2 resident）
blockWrite(a, idxBuf, consumed);
consumed = 0;
}
// 3. 溢出桶同樣按塊處理
overflowSortCached();
}4 性能對比（Intel Xeon Gold 6150，376 GB RAM）
| 算法 | 1e8 double (800 MB) | L3-miss / 寫 | 內存峯值 |
|---|---|---|---|
| Radix Sort | 2.1 s | 11 % | 2×n |
| Learned Sort 1.x | 2.7 s | 14 % | 1×n |
| Learned Sort 2.1 + Cache | 1.6 s | 6 % | 1×n |
排序速率 +50 %，且 內存原地（Radix 需 2×）。
5 扇出 & 閾值怎麼選（直接抄論文）
| 參數 | 公式 / 經驗值 | 説明 |
|---|---|---|
| 扇出 f | f = L2_SIZE / (16 × sizeof(Key)) |
保證 桶輔助表 ≤ L2/2 |
| 閾值 t | t = 100 | 溢出桶元素 < 5 % 時最優 |
| 預取距離 | 64 × cacheline | 提前 4 KB 拉線即可隱藏延遲 |
6 一句話帶走
Learned Sort 2.1 的緩存版 = “機器學習排大體，緩存塊寫細節”
無需額外內存，只要 按 L2 大小切分 + 預取 + L1 索引緩衝，
就能把 > L3 的大數據排序做到 比 Radix 還快 50 % ——
2025 年實測最快 非比較、原地 排序算法之一。
