代码

/*
References:
- saffah_codex_6a_agg3, https://duck.ac/submission/126205 : retain our accepted
  completed-stage register tail and the complete large sorting engine.
- saffah_codex_6a_agg3, https://duck.ac/submission/126198 : adapt its first-stage
  cursor convention, which stores the following record's end offset.
  All original author, source and license notices remain below.
Idea:
Encode each staging cursor three bytes ahead: load the next record's end
position directly for the flush test and payload address, and add three only
when saving the cursor for the next record. Adjust initialization and final
partial-record counting by the same three bytes. This moves an addition off
the dependency chain preceding each flush branch, with identical buffer
addresses, batches and capacity guards.
Purpose: Evaluate the dependency change on the officially faster register-tail
base, retaining every leaf sort and all output prefetches.
*/
/*
References:
- saffah_codex_6a_agg3, https://duck.ac/submission/126040 : retain the accepted
  192-byte first-stage staging layout and the entire 134M sorting engine.
- saffah_codex_6a_agg3, https://duck.ac/submission/126198 : adapt the completed
  batch's final three-byte record insertion into the last streaming vector.
  All inherited source credits and notices are retained below.
Idea:
For the 64th record of a staging batch, preserve byte 188 from record 63 and
insert the new record's low 24 bits directly into bytes 189..191 of the last
output vector. Do not write those bytes to staging before immediately loading
them back. Keep the same six streaming stores and all cursor/capacity logic.
Partial tails never consume bytes 189..191, so no staging repair is required.
Purpose: Transfer the officially positive ordinary staging technique to the
larger sorter while preserving its existing leaf algorithm and overflow path.
*/
/*
References:
- saffah_codex_6a_agg3, https://duck.ac/submission/125965 : retained full
  output-prefetch coverage and accepted sorting/overflow leaf kernels.
- saffah_codex_6s_agg2, https://duck.ac/submission/108912 : inherited the
  64-record three-byte staging and six-vector streaming flush mechanism.
- saffah_cc_v41_260924, https://duck.ac/submission/123019 : its related
  sorter also uses a 192-byte stage stride and exact three-byte flush tail;
  this independently derived implementation applies that shared principle
  to the present sorter without copying its implementation body.
- All original author references and notices remain below.
Idea:
Keep batches at 64 records, but use exactly 192 bytes per staging bucket
instead of a 320-byte stride. On the flush record write precisely its
three bytes with a u16 store and a byte store, so no fourth byte touches
the following bucket. Other records retain their four-byte overlapping
store. Every bucket and every flush stays 64-byte aligned; cursors and
partial-tail copies use the new stride. Reserve/fallback checks are kept.
Purpose: Reduce the stage span and avoid a cacheline touched solely by the
last-record overstore, without increasing flush frequency or partial lines.
*/
/*
References:
- saffah_codex_6a_agg3, https://duck.ac/submission/121941 : retained our
  uniform-high guard, fourteen-input network and overflow merge reuse.
- saffah_codex_6s_agg2, https://duck.ac/submission/108912 : restored its
  original sixteen-line output-prefetch span and lead. The inherited
  prefetch instruction is unchanged; all prior attribution remains below.
Idea:
Combine the accepted leaf algorithms with the public reference's original
output-prefetch coverage. Each 32-bucket group emits about one KiB; the
current half-KiB request span covers only half that typical output advance.
Restore the reference's one-KiB span starting two KiB ahead, preserving all
sorting, counters, data layouts, input prefetching and overflow handling.
Purpose: Test complete destination coverage with the newer leaf kernels,
rather than retrying the already-negative input-prefetch or staging changes.
*/
/*
References:
- saffah_codex_6a_agg3, https://duck.ac/submission/121442 : retained the
  accepted pruned-fourteen column sorter and complete radix partition engine.
- saffah_codex_6a_agg3, https://duck.ac/submission/121917 : adapted its exact
  uniform-high-byte guard and direct low-histogram output reconstruction.
- Earlier public authors, source URLs and notices remain below.
Idea:
On the existing oversized-column fallback, inspect the fully restored
high-byte count of the first leaf value. If it equals the entire leaf size,
all values share that high byte. Count only their 256 possible low bytes
and directly fill the sorted output, replacing the 65536-counter fallback.
Other overflow leaves retain the full original counting sort. The normal
column-network path performs no additional checks or histogram work.
Purpose: Apply the proven exact uniform-leaf shortcut to this separate
sorting engine, with full-output and dedicated leaf boundary verification.
*/
/* References:
- saffah_codex_6a_agg3, https://duck.ac/submission/121074: inherited byte-column
  sorter and overflow merge reuse, with all upstream notices retained below.
Idea: During existing cursor restoration, also record whether every column in
  a32-column group has at most14 entries. Such groups use the inherited16-input
  network specialized for two maximum-valued sentinel inputs: propagate these
  constants through comparators, leaving51 real comparisons instead of60.
  Retain the full network for groups with larger counts and all old fallbacks.
Experiment purpose: Reduce vector min/max operations and live registers in the
  common low-occupancy groups without introducing an extra count scan.
*/
/* References:
- saffah_codex_6s_agg2, https://duck.ac/submission/108912: inherited complete
  buffered radix implementation and network, source ancestry retained below.
- saffah_codex_6a_agg3, https://duck.ac/submission/120818: reduced prefetching
  and compact sentinel fill, retained unchanged.
Idea: For overflow columns containing17 or18 elements, reuse the16 values
  already sorted by the batched column network. Form the one/two remaining
  values in descending order with255 padding, then execute only the final
  five bitonic merge stages instead of sorting32 unsorted values from scratch.
Experiment purpose: Eliminate repeated work and strided reloads for the most
  common exceptional columns while preserving exact byte order and stores.
*/
// References:
// [1] saffah_codex_6s_agg2, https://duck.ac/submission/108552:
//     Reused our fastest accepted sorter with all inherited source citations.
// [2] saffah_cc_v41_agg1, https://duck.ac/submission/106899:
//     Original buffered MSD sorter inherited through #108552; no separate
//     license notice accompanied these public submissions.
// Approach:
// Let the packed workspace acquire backing pages on the first streaming
// writes rather than prepopulating its full capacity at sort entry. The
// bucket layout, writes, sorting, and output are unchanged.
// Purpose:
// Official experiment to determine whether skipping full workspace page
// population saves more than the first-touch faults cost at 2^27 elements.
// References:
// - saffah_codex_6s_agg2, https://duck.ac/submission/108148 : copied our fastest accepted 1001b engine, retaining its inherited citations below; no separate license notice appeared.
// - saffah_cc_v41_agg1, https://duck.ac/submission/106899 : original buffered MSD sorter inherited through #108148.
// - Judge Duck problem statement, https://duck.ac/problem/1001b : specifies that n is exactly 134,217,728.
// Approach: Specialize the outer sort() path and partition calls for the fixed problem size so the compiler sees a constant loop bound and bucket capacity. Retain an exact std::sort fallback for other lengths.
// Purpose: Experimental formal judged timing of whole-problem compile-time size specialization.
// References:
// [1] duck.ac user saffah_codex_6s_agg2, submission #108139, https://duck.ac/submission/108139: copied our full accepted sorter, changing only byte-one scatter compiler unroll factor.
// [2] duck.ac user saffah_cc_v41_agg1, submission #106899, https://duck.ac/submission/106899: inherited MSD radix engine as fully cited in [1]; public code has no separate license notice and attribution is preserved.
// Approach: Set four-at-a-time byte-one scatter unroll to 2 rather than 4 to further reduce hot-loop code footprint. Values retain identical per-bucket order and output.
// Purpose: Formal judged validation after official homepage eight-bucket test improved from 37.835364M to 37.537476M cycles with the same sorted output; test the current exact 1001b threshold.
// References:
// [1] duck.ac user saffah_cc_v41_agg1, submission #106899, https://duck.ac/submission/106899: copied its full accepted 1001b radix engine and modified one compiler unroll directive. The public submission has no separate license notice; author and source are credited, and its inherited attribution follows.
// [2] duck.ac user saffah_codex_6s_agg2, submission #106183, https://duck.ac/submission/106183: inherited AVX2 slow-column output code as described in [1].
// Approach: Lower the byte-one four-value scatter unroll factor from 16 to 4. The loop has random L1 cursor and column writes; a smaller body improves instruction-cache locality without altering the value order or bucket positions.
// Purpose: Formal judged experiment after the duck.ac homepage eight-bucket test improved from 39.539912M to 37.835364M cycles with identical sorted output. Check whether the complete 2^27-item case meets the current exact threshold.
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #106866 <https://duck.ac/submission/106866>
//     用途：**本文件正文 = #106866 的完整源码**（本地副本 `work/b1v_emit.cpp`），只改 `sort_leaf`
//     的 byte1 散列趟取数形态（见思路段）。#106866 之前的本账号上游链：
//     1.1 <https://duck.ac/submission/106861> 本账号 —— [MSET32]。
//     1.2 <https://duck.ac/submission/106840> 本账号 —— byte2 趟分块 + [PFSRC6]。
//     1.3 <https://duck.ac/submission/106285> / <https://duck.ac/submission/106201> 本账号 —— pad/capacity 与 s2_ 基座。
//     1.4 <https://duck.ac/submission/101817> duck.ac 用户 codex_astra —— `partition`/`sort_leaf` 血统。
//     1.5 <https://duck.ac/submission/105161> 本账号（1001，已达标）—— [PFSRC6]/[MSET32] 来源。
//     1.6 <https://duck.ac/submission/106183> duck.ac 用户 saffah_codex_6s_agg2 —— 慢列向量化发射片段来源。
//     1.7 <https://duck.ac/problem/1001b> 题目页（sort 2^27 个 u32，单测试点）。
// [2] 本账号工作区工件 `work/b1v_mb1.cpp`（本席自写的隔离微基准，**未提交**）——本发刀型的本地依据。
// ======================
// ===== 思路 =====
// **单变量（一处）：`sort_leaf` 的 byte1 散列趟由"逐元素 16 位取数"改成"4 元素/次 64 位取数"。**
//   * 原形态：`U32 v = load<U16>(src+i), h = v>>8, slot = count[h]; count[h]=slot+256; columns[slot]=Byte(v);`
//     ⇒ 每元素 1 条 16 位 load + `mov/movzbl` 两条取高字节 + 游标 RMW + 1 字节存。
//   * 本形态：一次 `memcpy(&q, src+i, 8)` 出 4 个元素，高字节用 `(q>>8k)&0xff` 直接取
//     ⇒ 每元素 0.25 条 load，取高字节的指令数同为 1，游标/数据存不变。
//   * 依据：本席隔离微基准（`work/b1v_mb1.cpp`：middle 1.29 MB / columns 2 MB / count 1 KB 全部 L1-L2 驻留、
//     7 轮取 min）**2.116 → 1.956 cycle/元素（−7.6%）**；同一台架里"目的地址换成 64 B 哑缓冲" = 1.221、
//     "删掉游标 store" = 1.511 ⇒ 该环的楼板 ~1.2，本刀取回其中约 1/5。
//   * 稳定性（LSD 基数排序的必需前提）：同一次 load 的 4 个元素按**低到高**处理，与逐元素版
//     逐位同序 ⇒ 桶内写入顺序逐位不变 ⇒ 输出逐位不变（仍按纪律在生产 n 跑逐元素闸门）。
// 提交目的 = **定价 + 兑现**（缺口 0.809895 ms）。判据 = 与 `#106866`（455.971702 ms）单变量比。
// ★ 声明：只改取数/取字节的形态，不改布局/算法/数据流；失败只关掉这一条路。
// ================
// ===== REFERENCES =====
// [1] duck.ac 用户 saffah_cc_v41_agg1（本账号），提交 #106861 <https://duck.ac/submission/106861>
//     用途：**本文件正文 = #106861 的完整源码**（本地副本 `work/b1v_m32.cpp`），只改 `sort_leaf`
//     慢列（`count[h] ∈ [17,32]`）的输出发射形态（见思路段）。#106861 之前的本账号上游链一并列出：
//     1.1 <https://duck.ac/submission/106840> 本账号 —— byte2 散列趟分块 + 6 条 `__builtin_prefetch(r+512..832)`。
//     1.2 <https://duck.ac/submission/106285> 本账号 —— BSS pad 2752 + `capacity` 末尾 `+BS`。
//     1.3 <https://duck.ac/submission/106201> 本账号 —— 其直接上游（s2_ 的 SIMD 网络件）。
//     1.4 <https://duck.ac/submission/101817> duck.ac 用户 codex_astra —— `partition`/`sort_leaf`/
//         16 输入网络来源。
//     1.5 <https://duck.ac/submission/105161> 本账号（1001，n=1e8，已达标）—— [PFSRC6] 预取参数与
//         [MSET32] 哨兵填充写法的**直接复制**来源。
//     1.6 <https://duck.ac/problem/1001b> 题目页（sort 2^27 个 u32，单测试点）。
// [2] duck.ac 用户 saffah_codex_6s_agg2，提交 #106183 <https://duck.ac/submission/106183>
//     用途：**直接复制**其 `sort_leaf` 慢列的向量化发射片段（`vlo/vhi` 拆分 + 3~4 条
//     `vpmovzxbd`+`vpor`+`vmovdqu`，以及 `end-dst >= (c<=24?24:32)` 的边界守卫与标量回退）。
//     该用户的文件自述其上游为本账号 #104352、#106150、#106157（本账号的 AVX2 网络/四向量发射）。
//     2.1 K. E. Batcher, "Sorting Networks and Their Applications" (1968)
//         <https://doi.org/10.1145/1468075.1468121> —— 仅用于确认本件沿用的 32 字节网络是合法排序网络
//         （未改动其比较器序列）。
// [3] Intel 64 与 IA-32 架构软件开发手册 <https://www.intel.com/sdm>
//     用途：确认 `PREFETCHh` 不触发异常、`vmovdqa`/`vpmovzxbd`/`vpsrldq`/`vmovdqu` 的语义与写边界。
// ======================
// ===== 思路 =====
// **单变量（一处）：`sort_leaf` 慢列（`count[h]` ∈ [17,32]）的发射由"逐元素标量存"改成向量化发射。**
//   * 原形态：`sort32_byte` 的结果先 `vmovdqu` 存回 `copy[32]`，再
//     `for(j=0;j<c;++j) dst[j]=base|(h<<8)|copy[j]` ⇒ 每列约 2 条向量 op + **c 条标量 load + c 条标量 store**
//     （c≈19 ⇒ ~40 条内存操作/列）。
//   * 本形态（引用 [2] 的片段）：`sorted` 留在寄存器里，`vpmovzxbd` 一次把 8 个字节扩成 8×u32、
//     `vpor` 上前缀、`vmovdqu` 32B 存出 ⇒ **每列 3~4 条（8 值/条）**，且省掉"存回 copy 再逐元素读"。
//     守卫 `end-dst >= (c<=24?24:32)` 保证靠近数组末尾时退回标量路径（不越界写）。
//   * 定价依据：该慢列路径在本题 **58662 次/场**（我方件内注释的实测计数）；原形态 ~100 uops/次、
//     新形态 ~16 uops/次 ⇒ 省 ≈4.9M uops ≈ 1.25 Mcyc ≈ **0.35 ms 量级**（缺口为 0.869063 ms）。
//   * 输出逐位不变：两条路径写入的 `dst[0..c-1]` 完全相同（`sorted` 的前 c 个字节 = 该列升序前 c 个）；
//     向量路径多写的 (24-c) 个位置被同一 `dst += c` 推进的下一个桶覆盖，数组末尾由守卫排除 ✓
//     ⇒ 仍按纪律在生产 n（2^27）跑逐元素闸门。
// 提交目的 = **定价 + 兑现**。判据 = 与 `#106861`（456.030870 ms）单变量比。
// ★ 声明：只改慢列的发射指令形态；失败只关掉这一条路。
// ================
#pragma GCC optimize("O3,unroll-loops,no-strict-aliasing")
#pragma GCC target("avx2,bmi,bmi2,popcnt")
#include <immintrin.h>
#include <algorithm>
#include <cstring>
#include <cstdint>
#include <utility>
#include <unistd.h>
#if defined(__APPLE__)
#define syscall(...) ((long)-1)
#endif
#ifndef BUFFER_BITS
#define BUFFER_BITS 6
#endif
#ifndef TOP_BITS
#define TOP_BITS 8
#endif
#ifndef UNROLL
#define UNROLL 1
#endif
static constexpr unsigned TB=TOP_BITS, K=1u<<TB, BS=1u<<BUFFER_BITS;
static constexpr unsigned NPORT = 134217728u;
alignas(64) static unsigned char workspace[3u*(256u*557056u + 256u*64u) + 4096u + 16u];
alignas(256) static unsigned char staging_bytes[K*192];
static unsigned byte_cursor[K];
alignas(64) static unsigned hist[K], starts[K], pos[K];
static inline unsigned read24(const unsigned char *s){unsigned x;memcpy(&x,s,4);return x&0xffffff;}
static void small_original(unsigned char*s,unsigned*d,unsigned n,unsigned prefix,unsigned*){
for(unsigned i=0;i<n;++i)d[i]=prefix|read24(s+3*i);
std::sort(d,d+n);
}
#define SM7_PAD (2752u)
static_assert(SM7_PAD == 2752u, "sm7_pad config echo");
alignas(64) static unsigned char sm7_pad[SM7_PAD] __attribute__((used));
static_assert(sizeof(sm7_pad) == SM7_PAD, "sm7_pad size echo");
alignas(2097152) static uint16_t middle[1<<21];
namespace fastsort {
constexpr unsigned kRadix=256;
constexpr unsigned kLeafLimit = 8192;
using U32 = unsigned; using Byte = uint8_t; using U16 = uint16_t; using U64 = uint64_t;
using Vec256 = __m256i; using Vec128 = __m128i;
template <class T> inline T load(const void *src) { T value; std::memcpy(&value, src, sizeof value); return value; }
template <class F, size_t... I> [[gnu::always_inline]] inline void each(F &&f, std::index_sequence<I...>) {
(f(std::integral_constant<size_t, I>{}), ...);
}
template <size_t N, class F> [[gnu::always_inline]] inline void repeat(F &&f) {
each(std::forward<F>(f), std::make_index_sequence<N>{});
}
}
// ===== s2_: SIMD 32-byte sorting network (see s2_mknet.py) =====
namespace s2_net {
alignas(32) static const unsigned char shuf[4][32] = {
  {1,0,3,2,5,4,7,6,9,8,11,10,13,12,15,14,1,0,3,2,5,4,7,6,9,8,11,10,13,12,15,14},
  {2,3,0,1,6,7,4,5,10,11,8,9,14,15,12,13,2,3,0,1,6,7,4,5,10,11,8,9,14,15,12,13},
  {4,5,6,7,0,1,2,3,12,13,14,15,8,9,10,11,4,5,6,7,0,1,2,3,12,13,14,15,8,9,10,11},
  {8,9,10,11,12,13,14,15,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0,1,2,3,4,5,6,7},
};
alignas(32) static const signed char choose_min[15][32] = {
  {-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1},
  {-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1},
  {-1,0,-1,0,0,-1,0,-1,-1,0,-1,0,0,-1,0,-1,-1,0,-1,0,0,-1,0,-1,-1,0,-1,0,0,-1,0,-1},
  {-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1},
  {-1,-1,0,0,-1,-1,0,0,0,0,-1,-1,0,0,-1,-1,-1,-1,0,0,-1,-1,0,0,0,0,-1,-1,0,0,-1,-1},
  {-1,0,-1,0,-1,0,-1,0,0,-1,0,-1,0,-1,0,-1,-1,0,-1,0,-1,0,-1,0,0,-1,0,-1,0,-1,0,-1},
  {-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1},
  {-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1},
  {-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1},
  {-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1},
  {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
  {-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0,-1,-1,-1,-1,-1,-1,-1,-1,0,0,0,0,0,0,0,0},
  {-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0,-1,-1,-1,-1,0,0,0,0},
  {-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0,-1,-1,0,0},
  {-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0,-1,0},
};
static inline __m256i sort32_byte(__m256i v){
  __m256i p0=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo0=_mm256_min_epu8(v,p0),hi0=_mm256_max_epu8(v,p0);
  v=_mm256_blendv_epi8(hi0,lo0,_mm256_load_si256((const __m256i*)choose_min[0]));
  __m256i p1=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
  __m256i lo1=_mm256_min_epu8(v,p1),hi1=_mm256_max_epu8(v,p1);
  v=_mm256_blendv_epi8(hi1,lo1,_mm256_load_si256((const __m256i*)choose_min[1]));
  __m256i p2=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo2=_mm256_min_epu8(v,p2),hi2=_mm256_max_epu8(v,p2);
  v=_mm256_blendv_epi8(hi2,lo2,_mm256_load_si256((const __m256i*)choose_min[2]));
  __m256i p3=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[2]));
  __m256i lo3=_mm256_min_epu8(v,p3),hi3=_mm256_max_epu8(v,p3);
  v=_mm256_blendv_epi8(hi3,lo3,_mm256_load_si256((const __m256i*)choose_min[3]));
  __m256i p4=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
  __m256i lo4=_mm256_min_epu8(v,p4),hi4=_mm256_max_epu8(v,p4);
  v=_mm256_blendv_epi8(hi4,lo4,_mm256_load_si256((const __m256i*)choose_min[4]));
  __m256i p5=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo5=_mm256_min_epu8(v,p5),hi5=_mm256_max_epu8(v,p5);
  v=_mm256_blendv_epi8(hi5,lo5,_mm256_load_si256((const __m256i*)choose_min[5]));
  __m256i p6=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[3]));
  __m256i lo6=_mm256_min_epu8(v,p6),hi6=_mm256_max_epu8(v,p6);
  v=_mm256_blendv_epi8(hi6,lo6,_mm256_load_si256((const __m256i*)choose_min[6]));
  __m256i p7=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[2]));
  __m256i lo7=_mm256_min_epu8(v,p7),hi7=_mm256_max_epu8(v,p7);
  v=_mm256_blendv_epi8(hi7,lo7,_mm256_load_si256((const __m256i*)choose_min[7]));
  __m256i p8=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
  __m256i lo8=_mm256_min_epu8(v,p8),hi8=_mm256_max_epu8(v,p8);
  v=_mm256_blendv_epi8(hi8,lo8,_mm256_load_si256((const __m256i*)choose_min[8]));
  __m256i p9=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo9=_mm256_min_epu8(v,p9),hi9=_mm256_max_epu8(v,p9);
  v=_mm256_blendv_epi8(hi9,lo9,_mm256_load_si256((const __m256i*)choose_min[9]));
  __m256i p10=_mm256_permute2x128_si256(v,v,0x01);
  __m256i lo10=_mm256_min_epu8(v,p10),hi10=_mm256_max_epu8(v,p10);
  v=_mm256_blendv_epi8(hi10,lo10,_mm256_load_si256((const __m256i*)choose_min[10]));
  __m256i p11=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[3]));
  __m256i lo11=_mm256_min_epu8(v,p11),hi11=_mm256_max_epu8(v,p11);
  v=_mm256_blendv_epi8(hi11,lo11,_mm256_load_si256((const __m256i*)choose_min[11]));
  __m256i p12=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[2]));
  __m256i lo12=_mm256_min_epu8(v,p12),hi12=_mm256_max_epu8(v,p12);
  v=_mm256_blendv_epi8(hi12,lo12,_mm256_load_si256((const __m256i*)choose_min[12]));
  __m256i p13=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
  __m256i lo13=_mm256_min_epu8(v,p13),hi13=_mm256_max_epu8(v,p13);
  v=_mm256_blendv_epi8(hi13,lo13,_mm256_load_si256((const __m256i*)choose_min[13]));
  __m256i p14=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo14=_mm256_min_epu8(v,p14),hi14=_mm256_max_epu8(v,p14);
  v=_mm256_blendv_epi8(hi14,lo14,_mm256_load_si256((const __m256i*)choose_min[14]));
  return v;
}
static inline __m256i merge32_byte(__m256i v){
  __m256i p10=_mm256_permute2x128_si256(v,v,0x01);
  __m256i lo10=_mm256_min_epu8(v,p10),hi10=_mm256_max_epu8(v,p10);
  v=_mm256_blendv_epi8(hi10,lo10,_mm256_load_si256((const __m256i*)choose_min[10]));
  __m256i p11=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[3]));
  __m256i lo11=_mm256_min_epu8(v,p11),hi11=_mm256_max_epu8(v,p11);
  v=_mm256_blendv_epi8(hi11,lo11,_mm256_load_si256((const __m256i*)choose_min[11]));
  __m256i p12=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[2]));
  __m256i lo12=_mm256_min_epu8(v,p12),hi12=_mm256_max_epu8(v,p12);
  v=_mm256_blendv_epi8(hi12,lo12,_mm256_load_si256((const __m256i*)choose_min[12]));
  __m256i p13=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[1]));
  __m256i lo13=_mm256_min_epu8(v,p13),hi13=_mm256_max_epu8(v,p13);
  v=_mm256_blendv_epi8(hi13,lo13,_mm256_load_si256((const __m256i*)choose_min[13]));
  __m256i p14=_mm256_shuffle_epi8(v,_mm256_load_si256((const __m256i*)shuf[0]));
  __m256i lo14=_mm256_min_epu8(v,p14),hi14=_mm256_max_epu8(v,p14);
  v=_mm256_blendv_epi8(hi14,lo14,_mm256_load_si256((const __m256i*)choose_min[14]));
  return v;
}

}
using s2_net::sort32_byte;
using s2_net::merge32_byte;
namespace byte_sort {
using namespace fastsort;
[[gnu::noinline]] inline void counting_sort(const U16 *src, U32 n, U32 *dst, U32 base) {
alignas(64) U32 counts[65536] = {};
for (U32 i = 0; i < n; ++i) ++counts[load<U16>(src + i)];
for (U32 v = 0; v < 65536; ++v)
for (U32 c = counts[v]; c; --c) *dst++ = base | v;
}
[[gnu::noinline]] inline void uniform_high_sort(const U16 *src,U32 n,U32 *dst,U32 prefix){
  alignas(32) U32 low[256]={};
#pragma GCC unroll 8
  for(U32 i=0;i<n;++i)++low[load<U16>(src+i)&255u];
  prefix|=load<U16>(src)&0xff00u;
  for(U32 digit=0;digit<256;++digit){
    const U32 count=low[digit];std::fill_n(dst,count,prefix|digit);dst+=count;
  }
}
[[gnu::always_inline]] inline void transpose8(const Vec256 *x, Byte *out) {
Vec256 a[8], b[8];
#pragma GCC unroll 4
for (U32 i = 0; i < 4; ++i) {
a[2 * i] = _mm256_unpacklo_epi8(x[2 * i], x[2 * i + 1]);
a[2 * i + 1] = _mm256_unpackhi_epi8(x[2 * i], x[2 * i + 1]);
}
#pragma GCC unroll 2
for (U32 i = 0; i < 2; ++i) {
#pragma GCC unroll 2
for (U32 j = 0; j < 2; ++j) {
b[4 * i + 2 * j] = _mm256_unpacklo_epi16(a[4 * i + j], a[4 * i + j + 2]);
b[4 * i + 2 * j + 1] = _mm256_unpackhi_epi16(a[4 * i + j], a[4 * i + j + 2]);
}
}
#pragma GCC unroll 4
for (U32 i = 0; i < 4; ++i) {
Vec256 lo = _mm256_unpacklo_epi32(b[i], b[i + 4]);
Vec256 hi = _mm256_unpackhi_epi32(b[i], b[i + 4]);
_mm256_store_si256((Vec256 *)(out + 32 * i), _mm256_permute2x128_si256(lo, hi, 0x20));
_mm256_store_si256((Vec256 *)(out + 128 + 32 * i), _mm256_permute2x128_si256(lo, hi, 0x31));
}
}
[[gnu::always_inline]] inline void sort16_columns(const Byte *src, Byte *out, Byte *out2) {
Vec256 x[16];
repeat<16>([&](auto j) __attribute__((always_inline)) {
x[j] = _mm256_load_si256((const Vec256 *)(src + 256 * j));
});
#define CMP16(A,B) { Vec256 lo = _mm256_min_epu8(x[A], x[B]); \
x[B] = _mm256_max_epu8(x[A], x[B]); x[A] = lo; }
CMP16(0, 13)
CMP16(1, 12)
CMP16(2, 15)
CMP16(3, 14)
CMP16(4, 8)
CMP16(5, 6)
CMP16(7, 11)
CMP16(9, 10)
CMP16(0, 5)
CMP16(1, 7)
CMP16(2, 9)
CMP16(3, 4)
CMP16(6, 13)
CMP16(8, 14)
CMP16(10, 15)
CMP16(11, 12)
CMP16(0, 1)
CMP16(2, 3)
CMP16(4, 5)
CMP16(6, 8)
CMP16(7, 9)
CMP16(10, 11)
CMP16(12, 13)
CMP16(14, 15)
CMP16(0, 2)
CMP16(1, 3)
CMP16(4, 10)
CMP16(5, 11)
CMP16(6, 7)
CMP16(8, 9)
CMP16(12, 14)
CMP16(13, 15)
CMP16(1, 2)
CMP16(3, 12)
CMP16(4, 6)
CMP16(5, 7)
CMP16(8, 10)
CMP16(9, 11)
CMP16(13, 14)
CMP16(1, 4)
CMP16(2, 6)
CMP16(5, 8)
CMP16(7, 10)
CMP16(9, 13)
CMP16(11, 14)
CMP16(2, 4)
CMP16(3, 6)
CMP16(9, 12)
CMP16(11, 13)
CMP16(3, 5)
CMP16(6, 8)
CMP16(7, 9)
CMP16(10, 12)
CMP16(3, 4)
CMP16(5, 6)
CMP16(7, 8)
CMP16(9, 10)
CMP16(11, 12)
CMP16(6, 7)
CMP16(8, 9)
#undef CMP16
transpose8(x, out);
transpose8(x + 8, out2);
}
[[gnu::always_inline]] inline void sort14_columns(const Byte*src,Byte*out,Byte*out2){
Vec256 v[14];
repeat<14>([&](auto j) __attribute__((always_inline)){v[j]=_mm256_load_si256((const Vec256*)(src+256*j));});
#define CMP14(A,B) {Vec256 lo=_mm256_min_epu8(v[A],v[B]);v[B]=_mm256_max_epu8(v[A],v[B]);v[A]=lo;}
CMP14(0,13)
CMP14(1,12)
CMP14(4,8)
CMP14(5,6)
CMP14(7,11)
CMP14(9,10)
CMP14(0,5)
CMP14(1,7)
CMP14(2,9)
CMP14(3,4)
CMP14(6,13)
CMP14(11,12)
CMP14(0,1)
CMP14(2,3)
CMP14(4,5)
CMP14(6,8)
CMP14(7,9)
CMP14(10,11)
CMP14(12,13)
CMP14(0,2)
CMP14(1,3)
CMP14(4,10)
CMP14(5,11)
CMP14(6,7)
CMP14(8,9)
CMP14(1,2)
CMP14(3,12)
CMP14(4,6)
CMP14(5,7)
CMP14(8,10)
CMP14(9,11)
CMP14(1,4)
CMP14(2,6)
CMP14(5,8)
CMP14(7,10)
CMP14(9,13)
CMP14(2,4)
CMP14(3,6)
CMP14(9,12)
CMP14(11,13)
CMP14(3,5)
CMP14(6,8)
CMP14(7,9)
CMP14(10,12)
CMP14(3,4)
CMP14(5,6)
CMP14(7,8)
CMP14(9,10)
CMP14(11,12)
CMP14(6,7)
CMP14(8,9)
#undef CMP14
Vec256 x[16]={v[0],v[1],v[2],v[3],v[4],v[5],v[6],v[7],v[8],v[9],v[10],v[11],v[12],v[13],_mm256_set1_epi8(-1),_mm256_set1_epi8(-1)};
transpose8(x,out);transpose8(x+8,out2);
}
[[gnu::always_inline]] inline U32 restore_counts(U32 *count, U32 *exceptional) {
U32 *end = count + 256; U32 over;
const Vec256 limit14 = _mm256_set1_epi32(14), limit16 = _mm256_set1_epi32(16), limit32 = _mm256_set1_epi32(32);
__asm__ volatile("vpxor %%ymm4, %%ymm4, %%ymm4\n\t"
".p2align 4\n\t1:\n\t"
".irp reg,0,1,2,3; vmovdqa 32*\\reg(%[count]), %%ymm\\reg; .endr\n\t"
".irp reg,0,1,2,3; vpsrld $8, %%ymm\\reg, %%ymm\\reg; .endr\n\t"
".irp reg,0,1,2,3; vmovdqa %%ymm\\reg, 32*\\reg(%[count]); .endr\n\t"
"vpmaxud %%ymm1, %%ymm0, %%ymm0; vpmaxud %%ymm3, %%ymm2, %%ymm2\n\t"
"vpmaxud %%ymm2, %%ymm0, %%ymm0\n\t"
"vpcmpgtd %[limit16], %%ymm0, %%ymm1\n\t"
"vmovmskps %%ymm1, %%eax\n\t"
"vpcmpgtd %[limit14], %%ymm0, %%ymm1; vmovmskps %%ymm1, %%ecx\n\t"
"shll $8, %%ecx; orl %%ecx, %%eax; movl %%eax, (%[flags])\n\t"
"vpmaxud %%ymm0, %%ymm4, %%ymm4\n\t"
"addq $128, %[count]; addq $4, %[flags]\n\t"
"cmpq %[end], %[count]; jb 1b\n\t"
"vpcmpgtd %[limit32], %%ymm4, %%ymm0; vmovmskps %%ymm0, %k[over]\n\t"
: [count] "+&r"(count), [flags] "+&r"(exceptional), [over] "=&r"(over)
: [end] "r"(end), [limit14] "x"(limit14), [limit16] "x"(limit16), [limit32] "x"(limit32)
: "rax", "rcx", "ymm0", "ymm1", "ymm2", "ymm3", "ymm4", "cc", "memory");
return over;
}
[[gnu::always_inline]] inline U32 *emit32_buckets16(const Byte *first, const Byte *second, const U32 *count,
U32 *dst, Vec256 prefix) {
const Vec256 step = _mm256_set1_epi32(256); const U32 *end = count + 32;
__asm__ volatile(".p2align 4\n\t1:\n\t"
".irp lane,0,1,2,3,4,5,6,7\n\t"
"movl 4*\\lane(%[count]), %%eax\n\t"
"vpmovzxbd 8*\\lane(%[first]), %%ymm1; vpmovzxbd 8*\\lane(%[second]), %%ymm2\n\t"
"vpor %[prefix], %%ymm1, %%ymm1; vpor %[prefix], %%ymm2, %%ymm2\n\t"
"vmovdqu %%ymm1, (%[dst]); vmovdqu %%ymm2, 32(%[dst])\n\t"
"leaq (%[dst],%%rax,4), %[dst]\n\t"
"vpaddd %[step], %[prefix], %[prefix]\n\t"
".endr\n\t"
"addq $64, %[first]; addq $64, %[second]; addq $32, %[count]\n\t"
"cmpq %[end], %[count]; jb 1b\n\t"
: [dst] "+&r"(dst), [prefix] "+&x"(prefix), [count] "+&r"(count), [first] "+&r"(first),
[second] "+&r"(second)
: [end] "r"(end), [step] "x"(step)
: "rax", "ymm1", "ymm2", "cc", "memory");
return dst;
}
inline void sort_leaf(const U16 *src, U32 n, U32 *dst, U32 base, U32 *end) {
if (n < 64) {
U32 copy[64];
for (U32 i = 0; i < n; ++i) copy[i] = base | load<U16>(src + i);
std::sort(copy, copy + n);
std::memcpy(dst, copy, n * 4); return;
}
if (n > kLeafLimit) return counting_sort(src, n, dst, base);
alignas(64) static Byte columns[kRadix * kLeafLimit];
alignas(64) U32 count[256];
/* [MSET32] 哨兵行填充 4096 B 由 `std::memset` 改成 128 条显式 32B `vmovdqa`。
   判题机 gcc 9.3 对已知长度的 memset 走 `rep stosq`；把「128 条 32B 存储」写成普通循环
   它也会折叠回 rep stosq（1001 已实测），故这里用 `asm volatile` 强制保持独立存储。
   每叶一次 x 65536 叶 = 268 MB 的填充。 */
{
  const __m256i sent = _mm256_set1_epi8((char)255);
  #pragma GCC unroll 4
  for (unsigned q = 0; q < 16u * kRadix; q += 32)
    __asm__ volatile("vmovdqa %1, %0" : "=m"(*(__m256i *)(columns + q)) : "x"(sent));
}
for (U32 i = 0; i < 256; ++i) count[i] = i;
/* [B1Q] 4 元素/次 64 位取数：`src` 是 u16 顺序流，原形态每元素 1 条 16 位 load +
   mov/movzbl 两条取高字节；本形态一次 64 位 load 出 4 个元素，高字节用移位直接取。
   本机隔离微基准（work/b1v_mb1.cpp，全 L1/L2 驻留、min-of-7）：2.116 -> 1.956 cyc/元素（-7.6%）。
   稳定性：桶内元素写入顺序与逐元素版逐位相同（同一次 load 的 4 个元素按低到高处理）⇒ 输出逐位不变。 */
{
U32 i = 0;
#pragma GCC unroll 2
for (; i + 4 <= n; i += 4) {
U64 q; std::memcpy(&q, src + i, 8);
U32 s;
s = count[(U32)(q >> 8) & 0xff];  count[(U32)(q >> 8) & 0xff] = s + 256;  columns[s] = (Byte)q;
s = count[(U32)(q >> 24) & 0xff]; count[(U32)(q >> 24) & 0xff] = s + 256; columns[s] = (Byte)(q >> 16);
s = count[(U32)(q >> 40) & 0xff]; count[(U32)(q >> 40) & 0xff] = s + 256; columns[s] = (Byte)(q >> 32);
s = count[(U32)(q >> 56) & 0xff]; count[(U32)(q >> 56) & 0xff] = s + 256; columns[s] = (Byte)(q >> 48);
}
#pragma GCC unroll 16
for (; i < n; ++i) {
U32 v = load<U16>(src + i), h = v >> 8, slot = count[h];
count[h] = slot + 256; columns[slot] = Byte(v);
}
}
U32 exceptional[8];
if (restore_counts(count, exceptional)) {
  if(count[load<U16>(src)>>8]==n)return uniform_high_sort(src,n,dst,base);
  return counting_sort(src,n,dst,base);
}
const Vec256 idx = _mm256_setr_epi32(0, 1, 2, 3, 4, 5, 6, 7);
for (U32 block = 0; block < 256; block += 32) {
alignas(32) Byte first[256], second[256];
#pragma GCC unroll 16
for(unsigned pf=0;pf<16;++pf)asm volatile("prefetchw %0"::"m"(*(const char*)((uintptr_t)dst+2048+64*pf)));
if ((exceptional[block >> 5] >> 8) == 0) sort14_columns(columns + block, first, second);
else sort16_columns(columns + block, first, second);
Vec256 prefix = _mm256_set1_epi32(base | (block << 8));
if ((exceptional[block >> 5] & 255) == 0 && end - dst >= 512) {
dst = emit32_buckets16(first, second, count + block, dst, prefix);
continue;
}
for (U32 i = 0; i < 32; ++i) {
U32 h = block + i, c = count[h];
if (__builtin_expect(c <= 16, 1)) {
Vec256 w0 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const Vec128 *)(first + 8 * i))), prefix);
Vec256 w1 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_loadl_epi64((const Vec128 *)(second + 8 * i))), prefix);
if (__builtin_expect(end - dst >= 16, 1)) {
_mm256_storeu_si256((Vec256 *)dst, w0);
_mm256_storeu_si256((Vec256 *)(dst + 8), w1);
} else {
_mm256_maskstore_epi32((int *)dst, _mm256_cmpgt_epi32(_mm256_set1_epi32((int)(c < 8u ? c : 8u)), idx), w0);
_mm256_maskstore_epi32((int *)(dst + 8), _mm256_cmpgt_epi32(_mm256_set1_epi32((int)(c > 8u ? c - 8u : 0u)), idx), w1);
}
} else {
Byte copy[32];
Vec256 sorted;
if(__builtin_expect(c<=18,1)){
  Vec128 lo=_mm_unpacklo_epi64(_mm_loadl_epi64((const Vec128*)(first+8*i)),
                              _mm_loadl_epi64((const Vec128*)(second+8*i)));
  unsigned a=columns[256*16+h],b=c==18?columns[256*17+h]:255;
  unsigned mn=a<b?a:b,mx=a<b?b:a;
  Vec128 hi=_mm_insert_epi16(_mm_set1_epi8(-1),(int)((mn<<8)|mx),7);
  sorted=merge32_byte(_mm256_set_m128i(hi,lo));
}else{
  for(U32 j=0;j<c;++j)copy[j]=columns[256*j+h];
  for(U32 j=c;j<32;++j)copy[j]=255;
  sorted=sort32_byte(_mm256_loadu_si256((const Vec256*)copy));
}
if (__builtin_expect(end - dst >= (c <= 24u ? 24u : 32u), 1)) {
  Vec128 vlo = _mm256_castsi256_si128(sorted), vhi = _mm256_extracti128_si256(sorted, 1);
  Vec256 x0 = _mm256_or_si256(_mm256_cvtepu8_epi32(vlo), prefix);
  Vec256 x1 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_srli_si128(vlo, 8)), prefix);
  Vec256 x2 = _mm256_or_si256(_mm256_cvtepu8_epi32(vhi), prefix);
  _mm256_storeu_si256((Vec256 *)(dst + 0), x0);
  _mm256_storeu_si256((Vec256 *)(dst + 8), x1);
  _mm256_storeu_si256((Vec256 *)(dst + 16), x2);
  if (__builtin_expect(c > 24u, 0)) {
    Vec256 x3 = _mm256_or_si256(_mm256_cvtepu8_epi32(_mm_srli_si128(vhi, 8)), prefix);
    _mm256_storeu_si256((Vec256 *)(dst + 24), x3);
  }
} else {
  _mm256_storeu_si256((__m256i *)copy, sorted);
  for (U32 j = 0; j < c; ++j) dst[j] = base | (h << 8) | copy[j];
}
// ---- (end) ---------------------------------------------------------------
}
dst += c;
prefix = _mm256_add_epi32(prefix, _mm256_set1_epi32(256));
}
}
}
}
static void small(unsigned char *__restrict s,unsigned *__restrict d,unsigned n,unsigned prefix,unsigned *array_end){
if(n<65536){small_original(s,d,n,prefix,array_end);return;}
unsigned mu=(n+255)/256;unsigned need=mu+(unsigned)(6.5*__builtin_sqrt((double)mu)+0.5)+8;unsigned odd=(need+31)/32;if(!(odd&1))odd++;unsigned cap=32u*odd;
if(cap>4096){small_original(s,d,n,prefix,array_end);return;}
unsigned mp[256];
for(unsigned k=0;k<256;k++)mp[k]=k*cap;
const unsigned char *r=s;const unsigned char *rend=s+3u*n;
while(r+192<=rend){
__builtin_prefetch(r+512,0,0);
__builtin_prefetch(r+576,0,0);
__builtin_prefetch(r+640,0,0);
__builtin_prefetch(r+704,0,0);
__builtin_prefetch(r+768,0,0);
__builtin_prefetch(r+832,0,0);
#pragma GCC unroll 16
for(unsigned j=0;j<64;++j,r+=3){
unsigned k=r[2];uint16_t value;memcpy(&value,r,2);
middle[mp[k]++]=value;
}
}
for(;r<rend;r+=3){
unsigned k=r[2];uint16_t value;memcpy(&value,r,2);
middle[mp[k]++]=value;
}
for(unsigned k=0;k<256;k++)if(mp[k]-k*cap>cap){small_original(s,d,n,prefix,array_end);return;}
for(unsigned k=0;k<256;k++){
unsigned count=mp[k]-k*cap,pre=prefix|(k<<16);
const uint16_t *src=middle+k*cap;
byte_sort::sort_leaf(src,count,d,pre,array_end);
d+=count;
}
}
template<bool Reserved> static bool partition(unsigned *__restrict a,unsigned n,unsigned capacity=0){
for(unsigned k=0;k<K;k++)byte_cursor[k]=k*192+3;
for(unsigned page=0;page<n;page+=1024){
if(page+5120<n)asm volatile("orl $0, %0" : "+m"(a[page+4112]));
unsigned stop=std::min(n,page+1024);
#pragma GCC unroll 16
for(unsigned i=page;i<stop;i++){
unsigned x=a[i],k=x>>24,o=byte_cursor[k];
if(__builtin_expect((o&63)==0,0)){
if(Reserved && pos[k]+64-starts[k]>capacity){_mm_sfence();return false;}
unsigned char *d=workspace+3*pos[k];
const unsigned char *src=staging_bytes+o-192;
const unsigned tail_word=(x<<8)|src[188];
__m256i last=_mm256_load_si256((const __m256i*)(src+160));
last=_mm256_blend_epi32(last,_mm256_set1_epi32((int)tail_word),0x80);
#pragma GCC unroll 5
for(unsigned j=0;j<160;j+=32)
_mm256_stream_si256((__m256i*)(d+j),_mm256_load_si256((const __m256i*)(src+j)));
_mm256_stream_si256((__m256i*)(d+160),last);
pos[k]+=64;o-=192;
}else memcpy(staging_bytes+o-3,&x,4);
byte_cursor[k]=o+3;
}
}
for(unsigned k=0;k<K;k++)pos[k]+=(byte_cursor[k]-k*192-3)/3;
_mm_sfence();
if(Reserved)for(unsigned k=0;k<K;k++)if(pos[k]-starts[k]>capacity)return false;
return true;
}
void sort(unsigned *a,int n){
{ static int done=0; if(!done){ done=1; /* workspace pages are faulted lazily */
  syscall(28,(void*)middle,sizeof(middle),14); } }
if(n!=(int)NPORT){std::sort(a,a+n);return;}
unsigned capacity=(((unsigned(NPORT)+K-1)/K*17/16+BS-1)&~(BS-1))+BS;
for(unsigned k=0;k<K;k++)starts[k]=pos[k]=k*capacity;
if(!partition<true>(a,NPORT,capacity)){
memset(hist,0,sizeof(hist));
for(int i=0;i<NPORT;i++)++hist[a[i]>>(32-TB)];
unsigned z=0;
for(unsigned k=0;k<K;k++){starts[k]=pos[k]=z;z=(z+hist[k]+BS-1)&~(BS-1);}
partition<false>(a,NPORT);
}
unsigned z=0;
for(unsigned k=0;k<K;k++){
unsigned size=pos[k]-starts[k];
memcpy(workspace+3*(pos[k]&~(BS-1)),staging_bytes+k*192,3*(pos[k]&(BS-1)));
small(workspace+3*starts[k],a+z,size,k<<24,a+NPORT);
z+=size;
}
}

评测结果