目录
一、归并排序
（一）算法思想
（二）代码实现
（三）复杂度与稳定性
二、非递归版本归并排序
（一）代码实现步骤
（二）排序示例展示图
（三）代码实现
三、外排序之文件归并排序实现
（一）外排序介绍
（二）代码实现步骤
（三）代码实现
（四）时间复杂度与稳定性分析
一、归并排序
（一）算法思想
归并排序基于 “分治法”，核心是 “先分后合”：
1、分解
将数组递归二分，直至每个子区间仅含一个元素（视为有序）。
例如数组 [5,3,9,6,2,4,7,1,8]，分解为 [5]、[3]、[9]、[6]、[2]、[4]、[7]、[1]、[8]。
2、合并
将两个相邻的有序子区间合并为一个有序区间，重复合并直至得到完整有序数组。例如 [5] 与 [3] 合并为 [3,5]，[9] 与 [6] 合并为 [6,9]，再合并 [3,5] 与 [6,9] 为 [3,5,6,9]，以此类推。
（二）代码实现
1、具体操作图
（1）简略版
（2）完整版★（保姆版）
2、具体代码
（1）分解阶段
_MergeSort递归二分数组，如n = 9时，mid = (0 + 8) / 2 = 4，左区间 [0,4]、右区间 [5,8]，继续二分直至每个区间长度为 1。
（2）合并阶段
Merge函数合并两个有序区间，如合并 [0,0]（5）与 [1,1]（3）为 [3,5]，合并 [2,2]（9）与 [3,3]（6）为 [6,9]，再合并 [0,1]（3,5）与 [2,3]（6,9）为 [3,5,6,9]。
Tip：这里[0.0]（5）的意思是，最左边与最右边都是5，即只剩一个数据。
（3）临时数组作用
tmp用于暂存合并后的有序数据，避免原数组元素被覆盖，合并后再拷贝回原数组。
（4）代码的理解
在完整版的流程图中，已经清楚展示了分解的时机与合并的时机，所以在这里就不多作说明，我们来关注一下是怎么合并的。
我们将 begin1 指向第一个数组头部，end1 指向第一个数组尾部；begin2 指向第二个数组头部，end2 指向第二个数组尾部。
然后通过判断 begin1位置与 begin2 位置对应数据的大小，决定插入临时数组的数据是谁。插入之后，对应的 begin 就加 1，直到超过 end 为止。
一旦有一个数组遍历完成了，就退出第一个循环。然后剩下那个数组的数据，直接插到临时数组的尾部，从而完成数据的合并。
//只要涉及到二分，就会产生递归
//归并排序的递归算法
void _MergeSort(int* arr, int left, int right, int* tmp)
{
//1、分解
//递归结束的条件
if (left >= right)
return;
int mid = (left + right) / 2;
//根据mid 划分左右两个序列：[left,mid] [mid+1,right]
_MergeSort(arr, left, mid, tmp);
_MergeSort(arr, mid + 1, right, tmp);
//2、合并
//合并两个序列：[left,mid] [mid+1,right]
//创建临时数据，进行合并，然后再覆盖到原数组合
int begin1 = left, end1 = mid;
int begin2 = mid + 1, end2 = right;
int index = begin1;//作为临时数组移动的下表
while (begin1 <= end1 && begin2 <= end2)
{
//这里就是将两个数组合并为一个有序的数组
if (arr[begin1] <= arr[begin2])
tmp[index++] = arr[begin1++];
else
tmp[index++] = arr[begin2++];
}
//左序列数据没有全部放到tmp数组中
//右序列数据没有全部放到tmp数组中
while (begin1 <= end1)
tmp[index++] = arr[begin1++];
while (begin2 <= end2)
tmp[index++] = arr[begin2++];
//tmp中有序的数据导入原数组
for (int i = left; i <= right; i++)
arr[i] = tmp[i];
}
//归并排序
void MergeSort(int* arr, int n)
{
//因为不知道n的大小，所以要使用动态开辟内存
int* tmp = (int*)malloc(sizeof(int) * n);
_MergeSort(arr, 0, n – 1, tmp);
free(tmp);
tmp = NULL;
}
（三）复杂度与稳定性
1、时间复杂度
（1）分解阶段：递归深度O(logn)。
（2）合并阶段：每趟合并O(n)，总合并次数O(nlogn)。
（3）整体时间复杂度：O(nlogn)（最好、最坏、平均情况均为此复杂度）。
2、空间复杂度
O(n)（需申请大小为n的临时数组tmp）。
3、稳定性
稳定，合并时，若两个区间元素相等，优先选择左区间元素，保持相对顺序。
Tip：非递归版本的归并排序的复杂度和稳定性也是这样。
二、非递归版本归并排序
（一）代码实现步骤
递归版归并排序是自顶向下地将大数组不断分割为小数组，直到子数组长度为 1，再向上合并。而非递归版则采用自底向上的思路：
（1）先将数组中相邻的长度为 1的子数组两两合并，得到若干长度为 2 的有序子数组；
（2）再将相邻的长度为 2的子数组两两合并，得到若干长度为 4 的有序子数组；
（3）以此类推，直到合并出长度大于等于原数组长度的有序数组，排序完成。
这种 “从小到大一阶阶合并” 的策略，完全通过循环实现，避免了递归的函数调用开销。
（二）排序示例展示图
（三）代码实现
//非递归版本的归并排序
void MergeSortNonR(int* arr, int n)
{
if (n <= 1)
return;
int* tmp = (int*)malloc(sizeof(int) * n);
if (tmp == NULL)
{
perror("malloc fail!\\n");
exit(1);
}
// 自底向上合并：子数组长度从 1 开始，每次翻倍
int gap = 1;
while (gap < n)
{
// 根据当前 gap 分组，两两合并相邻子数组
for (int left = 0; left < n; left += 2 * gap)
{
int begin1 = left, end1 = left + gap – 1; // 左子数组的起止索引
int begin2 = left + gap, end2 = left + 2 * gap – 1; //右子数组的起止索引（可能越界）
// 处理越界：如果右子数组的起始位置已经超出数组长度，说明无右子数组可合并，直接跳出循环
// 主要是处理奇数个数据的情况
if (begin2 >= n)
break;
// begin2没有越界，那么说明最后一个序列还是有数据的，只是说不一定有gap个
// 此时将将 end2 修正为数组末尾
if (end2 >= n)
end2 = n – 1;
// 两个有序序列进行合并
// 临时数组 tmp 中当前填充的位置
int index = begin1;
while (begin1 <= end1 && begin2 <= end2)
{
//这里就是将两个数组合并为一个有序的数组
if (arr[begin1] <= arr[begin2])
tmp[index++] = arr[begin1++];
else
tmp[index++] = arr[begin2++];
}
//左序列数据没有全部放到tmp数组中
while (begin1 <= end1)
tmp[index++] = arr[begin1++];
//右序列数据没有全部放到tmp数组中
while (begin2 <= end2)
tmp[index++] = arr[begin2++];
// 将临时数组的结果复制回原数组
memcpy(arr + left, tmp + left, (end2 – left + 1) * sizeof(int));
}
gap *= 2; // 合并粒度翻倍
}
free(tmp);
tmp = NULL;
}
三、外排序之文件归并排序实现
（一）外排序介绍
1、什么是外排序
外排序是指能够处理极大量数据的排序算法。
通常来说，外排序处理的数据不能一次装入内存，只能放在读写较慢的外存储器（通常是硬盘）上。外排序通常采用的是一种"排序﹣归并"的策略。
在排序阶段，先读入能放在内存中的数据量，将其排序输出到一个临时文件，依此进行，将待排序数据组织为多个有序的临时文件。然后在归并阶段将这些临时文件组合为一个大的有序文件，也即排序结果。
跟外排序对应的就是内排序，我们之前讲的常见的排序，都是内排序，他们排序思想适应的是数据在内存中，支持随机访问。归并排序的思想不需要随机访问数据，只需要依次按序列读取数据，所以归并排序既是一个内排序，也是一个外排序。
2、为什么使用归并排序进行外排序
希尔排序、堆排序、快速排序，这些效率较高的排序方式，其实都只能在内存中处理数据。
因为它们都是要访问内存当中的一个下标位置的，磁盘可以支持我们访问某一个位置，但是你不断得变换这个位置，性能会很慢。
它更适应的是序列式得去写或者读在这个地方。
即使是序列式的，都比内存慢很多，更不要说是随机的这种了，虽然接口上支持，但是完全是不可行的。
所以也就意味着其他排序的思想，当你有大量数据在磁盘上时，这些思想都用不上。那为什么归并排序可以呢？
因为归并的思想是不需要进行下标位置的随机访问的，只需要线性得挨着读和写即可，将两个有序的数据，写入一个新数组，使其中内容都变得有序。
（二）代码实现步骤
归并要求数列是有序的，但是不要求数列元素的个数相同。
我们可以把一个大文件，变成很多个小文件，然后把这些小文件里面的内容变得有序。方法是：此时小文件，可以写入内存，在内存中变得有序，然后将他两两归并即可。
但是这种思路不那么好实现，因为创建了中间这些小文件，你也不知道分成多少份，具体的文件大小你是不可控的，这个思路没有这么好。具体的实现思路如下：
第一步：读取 n 个值排序后写到file1，再读取n个值排序后写到file2。（这里的排序是在内存中排序，选择尽可能块的排序方式即可，这个 n 可以取大一些，但是尽量要让内存可以放下）
第二步：file1 和 file2利用归并排序的思想，依次读取比较，取小的尾插到 mfile，mfile 归并为一个有序文件
第三步：将 file1 和 file2 删掉，mfile 重命名为 mfile1
第四步：再次读取 n 个数据排序后写到 file2
第五步：继续 file1 和 file2 归并，重复步骤2，直到文件中无法读出数据。最后归并出的有序数据放到了 file1 中。（最后一个 file2 不一定有 n 个数据）
Tip：下图还有最后一步没有描述到位，最后还要删除file1，再删除file2，mfile 重命名为 mfile1，再尝试从 file 中读取数据，没有读取到，则程序结束，排序完成。
（三）代码实现
1、先创建N个随机数，写到文件中
// 生成N个随机整数并写入文件data.txt
void CreateDate()
{
//造数据
int n = 10000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL) { perror("fopen error"); return; }
for (int i = 0; i < n; i++)
{
// 生成随机数：rand()的范围有限（0~RAND_MAX，通常为32767）
// 此处加上循环变量i，目的是减少随机数重复的概率（尤其当n较大时）
int x = rand() + i;
// 将生成的整数以换行分隔的形式写入文件
fprintf(fin, "%d\\n", x);
}
fclose(fin);
}
2、将部分数据写到内容，进行排序，再写回小文件
// 比较函数，用于qsort的升序排序
int compare(const void* a, const void* b)
{
return (*(int*)a – *(int*)b);
}
// 从文件读取n个数据，内存排序后写入新文件
// 返回实际读取的数据个数，无数据返回0
// 一般情况下返回n，最后一次可能不足n个，所以返回值用j表示
int ReadDataSortToFile(FILE* fout, int n, const char* file1)
{
// 动态开辟数组存储数据
int* arr = malloc(sizeof(int) * n);
if (arr == NULL) { perror("malloc error"); return 0; }
// 目标是读取n个数据之后排序，如果遇到文件结束，应该读到j个数据
int x = 0;
int j = 0; // 记录实际读取的数据个数
for (int i = 0; i < n; i++)
{
// 读取数据，遇文件结束则终止
if (fscanf(fout, "%d\\n", &x) == EOF)
break;
arr[j++] = x;
}
// 无数据可读时释放资源并返回
if (j == 0)
{
free(arr);
arr = NULL;
return 0;
}
// 对读取的数据进行排序
qsort(arr, j, sizeof(int), compare);
// 打开目标文件用于写入
FILE* fin = fopen(file1, "w");
if (fin == NULL) { free(arr); arr = NULL; perror("fopen error"); return 0; }
// 将排序后的数据写入文件
for (int i = 0; i < j; i++)
fprintf(fin, "%d\\n", arr[i]);
// 释放资源并关闭文件
free(arr);
arr = NULL;
fclose(fin);
return j;
}
3、对于两个小文件进行归并排序，合成一个较大的文件，同时删除掉两个小文件
// 归并两个有序文件到目标文件
void MergeFile(const char* file1, const char* file2, const char* mfile)
{
// 打开第一个源文件（只读）
FILE* fout1 = fopen(file1, "r");
if (fout1 == NULL) { perror("fopen error"); return; }
// 打开第二个源文件（只读）
FILE* fout2 = fopen(file2, "r");
if (fout2 == NULL) { perror("fopen error"); return; }
// 打开目标归并文件（只写）
FILE* mfin = fopen(mfile, "w");
if (mfin == NULL) { perror("fopen error"); return; }
// 依次读取
// 使用归并逻辑：谁小谁写入，谁没完谁尾插
// 读取两个文件的首个数据，ret记录是否读到，x1与x2记录读到的值
int x1 = 0, x2 = 0;
int ret1 = fscanf(fout1, "%d", &x1);
int ret2 = fscanf(fout2, "%d", &x2);
// 归并核心逻辑：比较两个文件当前数据，小的写入目标文件并读取下一个数据
// 写入之后，立刻读取该文件下一个数据，用于接下来的比较
// 文件的读取是有记忆的，光标会跟随移动，所以读取的就是下一个数据。
while (ret1 != EOF && ret2 != EOF)
{
if (x1 <= x2)
{
fprintf(mfin, "%d\\n", x1);
ret1 = fscanf(fout1, "%d", &x1);
}
else
{
fprintf(mfin, "%d\\n", x2);
ret2 = fscanf(fout2, "%d", &x2);
}
}
// 处理第一个文件剩余数据
while (ret1 != EOF)
{
fprintf(mfin, "%d\\n", x1);
ret1 = fscanf(fout1, "%d", &x1);
}
// 处理第二个文件剩余数据
while (ret2 != EOF)
{
fprintf(mfin, "%d\\n", x2);
ret2 = fscanf(fout2, "%d", &x2);
}
// 关闭所有文件
fclose(fout1);
fclose(fout2);
fclose(mfin);
}
4、主函数对它们依次调用
int main()
{
// 1、生成初始随机数据文件data.txt
CreateDate();
// 2、读到内容排序，并写入小文件
const char* file1 = "file1.txt"; // 归并过程中的临时文件1
const char* file2 = "file2.txt"; // 归并过程中的临时文件2
const char* mfile = "mfile.txt"; // 归并结果的临时文件
// 打开原始数据文件（只读）
FILE* fout = fopen("data.txt", "r");
if (fout == NULL) { perror("fopen error"); return 0; }
// 先读取两批数据到file1和file2，每批100个并排序
int num = 100;
int count1 = ReadDataSortToFile(fout, num, file1);
int count2 = ReadDataSortToFile(fout, num, file2);
//3、进行归并排序
// 若只有一批数据，直接作为结果（无需归并）
if (count1 > 0 && count2 == 0)
{
fclose(fout);
return 0;
}
// 循环归并：每次归并file1和file2到mfile，再读取新数据到file2
while (count2 > 0)
{
MergeFile(file1, file2, mfile); // 归并两个有序文件
// 替换file1为归并结果，清理临时文件
remove(file1);
remove(file2);
rename(mfile, file1);
// 读取下一批数据到file2并排序
count2 = ReadDataSortToFile(fout, num, file2);
}
printf("排序完成，结果在 %s 中\\n", file1); // 输出结果文件信息
fclose(fout);
return 0;
}
（四）时间复杂度与稳定性分析
该代码实现了外部排序，核心步骤为：
① 生成随机数据文件 data.txt（10000 个数据）。
② 分批次读取数据到内存，每批 num=100 个，排序后写入临时文件 file1.txt 或 file2.txt。
③ 循环归并两个临时文件到 mfile.txt，替换 file1.txt 为归并结果，直到所有数据处理完毕，最终结果保存在 file1.txt 中。
1、时间复杂度分析
（1）整体流程拆解
外部排序的时间复杂度由两部分构成：内存排序时间 + 归并时间。
在这个代码中，总数据量为 N（此处 N=10000）；每批读取到内存排序的数据量为 B（此处 B=100）；临时文件数量为 k = N/B（向上取整，此处 k=100）。
（2）各阶段时间复杂度
① 分批内存排序（ReadDataSortToFile）
每次读取 B 个数据，用 qsort（快速排序）排序，单批排序时间为 O(B log B)；共需 k 批，总排序时间为 O(k * B log B) = O(N log B)，因为 k*B ≈ N。
代入数值：100・O (100 log 100) ≈ 100・(100×6.6) = O (66000)，属于低阶项。
② 归并阶段（MergeFile 循环）
归并过程是多轮两两归并：每次将 file1（已归并的结果）与 file2（新分块的排序数据）归并到 mfile，循环直到所有分块处理完毕。
第 1 次归并：M=B（第 1 块）+ 新块 B → 时间 O (B+B)=O (B)
第 2 次归并：M=2B（前 2 块合并结果）+ 新块 B → 时间 O (2B+B)=O (3B)
第 3 次归并：M=3B（前 3 块合并结果）+ 新块 B → 时间 O (3B+B)=O (4B)
…
第 K-1 次归并：M=(K-1) B（前 K-1 块合并结果）+ 新块 B → 时间 O ((K-1) B+B)=O (K・B)
归并时间总和是等差数列求和：O (B + 3B + 4B + … + K・B) ≈ O (K²・B)（忽略首项和系数，取最高阶项）。
因 K = N/B，代入得：O ((N / B)²・B) = O(N² / B)。
代入数值：O (10⁸/100)=O (10⁶)，是分块排序的 15 倍 +，属于高阶项。
（3）整体时间复杂度
分批内存排序（O (N log B)）是低阶项，累积归并 O(N² / B) 是主导项，因此整体时间复杂度为：O(N²/B)。
2、空间复杂度分析
内存中最大的额外空间是分块排序时开辟的数组 arr，大小为 num（固定值），此处的空间复杂度为O(num)，且与 n 无关。
函数中定义的局部变量（如 x、i、j 等）和文件指针，占用的空间是常数级，即 O(1)。
代码中使用了 file1.txt、file2.txt、mfile.txt 等临时文件存储分块排序结果和归并结果，这些文件的总大小最多为 O(N)，但属于外部存储，不纳入算法的空间复杂度分析。
因此整体空间复杂度为：O(num)（即 O(B)，B 为每批处理的数据量）。
3、稳定性分析
排序算法的稳定性取决于分块排序和归并两个步骤是否稳定：
（1）分块排序：使用 qsort（快速排序），不稳定。快速排序在交换元素时可能改变相等元素的相对顺序。
（2）归并过程：代码中归并逻辑为 if (x1 < x2) 时写入 x1，否则写入 x2；当 x1 == x2 时，优先写入 x1（来自 file1），这样保证了归并的稳定性。但由于 file1 和 file2 本身是不稳定排序的结果，因此整体不稳定。
以上即为 排序（四）“归并” 的全部内容，创作不易，麻烦三连支持一下呗~
