归并排序处理大数组需用原地迭代法：一次性分配O(n)辅助空间，分块合并避免递归栈溢出；超2GB改用unique_ptr或mmap；比较函数应noexcept且用memcmp；数据需64字节对齐。
归并排序在大数组上为什么容易崩
直接用递归版 merge_sort 处理几百 MB 的 std::vector<int></int>，大概率触发栈溢出或内存分配失败——递归深度 O(log n) 看似安全，但每层都要拷贝临时子数组，n=1e8 时仅一次 std::vector::resize 就可能卡住。更隐蔽的问题是：默认的 std::vector 在堆上连续分配，大数组容易遭遇内存碎片，std::bad_alloc 不是报错，是静默失败（比如 data.size() 突然变 0）。
必须用原地归并 + 迭代写法
所谓“原地”不是真不占额外空间，而是把辅助空间控制在 O(n) 且只申请一次；迭代则彻底避开递归栈。关键操作是分块合并：把数组切成固定大小的块（如 4096 元素/块），两两合并，再把块大小翻倍，循环直到全覆盖。
- 先用
std::vector<int> temp(n)</int>一次性分配好辅助空间，后续所有合并都复用它 - 外层循环控制块大小
size，从 1 开始，每次size *= 2 - 内层循环用
for (int left = 0; left 遍历左块起点，避免越界 - 合并时用双指针比较，把结果写入
temp对应位置，最后std::copy回原数组（或交替读写，省一次拷贝）
示例核心片段：
void iterative_merge_sort(std::vector<int>& data) {
int n = data.size();
std::vector<int> temp(n);
for (int size = 1; size < n; size *= 2) {
for (int left = 0; left < n - size; left += 2 * size) {
int mid = left + size - 1;
int right = std::min(left + 2 * size - 1, n - 1);
merge(data, temp, left, mid, right);
}
std::copy(temp.begin(), temp.begin() + n, data.begin());
}
}
处理超大数组（>2GB）要绕开 vector
std::vector 内部用 new[] 分配，32 位环境上限约 2GB，64 位虽无硬限制，但 vector::reserve 可能因地址空间碎片失败。此时该切到 std::unique_ptr<int></int> 或 mmap：
立即学习“C++免费学习笔记（深入）”；
- 用
std::unique_ptr<int> ptr(new int[n])</int>绕过 vector 的 size 检查和异常安全包装 - 若需处理几十 GB 文件，直接 mmap 到内存：
int* base = static_cast<int>(mmap(nullptr, len, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0))</int>，然后对base调用同套迭代归并逻辑 - 注意：mmap 后必须用
munmap，且合并时避免跨页频繁访问——把块大小设为 4KB 的整数倍（如 4096）能提升 TLB 命中率
性能陷阱：别信默认比较函数
对结构体或自定义类型排序时，std::less 默认调用 operator<，如果该操作涉及深拷贝或复杂计算（比如字符串比较），整个归并过程会慢 3–5 倍。实测过一个含 std::string 成员的 struct，改用 std::memcmp 直接比底层内存快 4.2 倍。
- 用
std::sort前先确认比较函数是否noexcept且constexpr - 对 POD 类型，强制用
std::memcmp(&a, &b, sizeof(T)) < 0替代重载操作符 - 编译加
-O2 -march=native，GCC 对std::copy和std::merge有向量化优化，没开优化时迭代归并比递归还慢
大数组归并最易被忽略的点：缓存行对齐。如果数据起始地址不是 64 字节对齐，CPU 每次读取都会多取一倍内存，posix_memalign 或 _aligned_malloc 强制对齐后，实测吞吐量提升 18%。
