自底向上归并排序如何避免每次合并时的数组拷贝操作

你现有实现的核心冗余开销是每次merge前都要把待归并块从原数组拷贝到临时缓冲区，这个问题在迭代版里完全可以通过双数组角色轮换的方式解决，思路和递归版本质一致，不需要依赖递归调用栈传参，只要按归并轮次切换源/目标数组即可。

现有实现问题 #

你当前的代码逻辑存在固定拷贝开销：每次执行merge前都执行memcpy(buf, a, len * sz)把待归并块全量拷到缓冲区，归并完成后再写回原数组，相当于每个元素在每一层归并中会被拷贝2次，排序大体积元素时开销很高。

优化实现思路 #

核心逻辑是让原数组和临时缓冲区交替作为归并的输入源和输出目标，彻底去掉merge前的前置拷贝：

• 维护两个指针src和dst，分别标记当前轮归并的输入数组、输出数组
• 初始时src指向原输入数组a，dst指向申请的临时缓冲区buf
• 修改merge函数：直接从src读取左右两个有序段的元素，按顺序归并后直接写入dst对应位置，不需要提前拷贝块内容
• 每完成一个宽度w的全量归并轮次，就交换src和dst的指针——下一轮归并直接以上一轮的输出作为输入，结果写回上一轮的输入数组
• 所有归并轮次结束后，如果最终排序结果不在原数组a里（即src不指向a），只需要执行一次全量拷贝把结果从缓冲区搬回原数组即可
• 原有的小段插入排序、有序块跳过的优化都可以保留，只需要适配双数组逻辑即可

需要注意的实现坑 #

1. 原有的「右段首元素>=左段尾元素则直接返回」的优化不能直接保留：这时候待归并块本身已经有序，但还是需要把src对应区间的内容拷贝到dst的对应位置，否则dst里该位置是旧数据，下一轮归并会出错。
2. 原merge函数里只需要拷贝剩余左段的逻辑不成立：旧逻辑因为提前把整个块拷到了buf，右段剩余元素本来就在原数组的正确位置所以不需要额外拷贝；双数组模式下，左右两段剩余的有序元素都要从src拷贝到dst。
3. 归并过程中遇到末尾不足2w长度的残块、甚至不足w长度的孤立块时，都要把块内容从src拷贝到dst对应位置，不能跳过。

修改后的核心代码参考 #

#include "sort.h"
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

#define CUTOFF 8
#define MIN(a, b) ((a) < (b) ? (a) : (b))

void merge(uint8_t *src, uint8_t *dst, size_t left, size_t mid, size_t right, size_t sz, cmpfn cmp);

void merge_sort(void *a, size_t len, size_t sz, cmpfn cmp) {
  if (len <= 1) return;
  uint8_t *buf = malloc(len * sz);
  uint8_t *src = (uint8_t*)a;
  uint8_t *dst = buf;

  // 初始小段用插入排序，直接在源数组上操作
  for (size_t i = 0; i < len; i += CUTOFF) {
    insertion_sort(src + i * sz, MIN(CUTOFF, len - i), sz, cmp);
  }

  for (size_t w = CUTOFF; w < len; w *= 2) {
    for (size_t i = 0; i < len; i += w * 2) {
      size_t mid = MIN(i + w, len);
      size_t block_end = MIN(i + 2 * w, len);
      merge(src, dst, i, mid, block_end, sz, cmp);
    }
    // 交换源和目标数组，下一轮归并方向反转
    uint8_t *tmp = src;
    src = dst;
    dst = tmp;
  }

  // 如果最终结果不在原数组，做一次全量拷贝搬回
  if (src != a) {
    memcpy(a, src, len * sz);
  }
  free(buf);
}

void merge(uint8_t *src, uint8_t *dst, size_t left, size_t mid, size_t right, size_t sz, cmpfn cmp) {
  // 块已经有序的情况，直接拷贝整个块到目标数组
  if (cmp(src + mid * sz, src + (mid - 1) * sz) >= 0) {
    memcpy(dst + left * sz, src + left * sz, (right - left) * sz);
    return;
  }

  size_t i = left, j = mid, k = left;
  while (i < mid && j < right) {
    if (cmp(src + j * sz, src + i * sz) < 0) {
      memcpy(dst + k * sz, src + j++ * sz, sz);
    } else {
      memcpy(dst + k * sz, src + i++ * sz, sz);
    }
    k++;
  }
  // 拷贝剩余的有序段
  if (i < mid) {
    memcpy(dst + k * sz, src + i * sz, (mid - i) * sz);
  }
  if (j < right) {
    memcpy(dst + k * sz, src + j * sz, (right - j) * sz);
  }
}

这个优化可以把归并排序的内存拷贝开销降低接近一半，元素体积越大（比如排序大结构体），收益越明显。

内容的提问来源于stack exchange，提问作者vim_overlord