归并是将两个或多个有序记录序列合并成一个有序序列。归并方法有多种，一次对两个有序记录序列进行归并，称为二路归并排序，也有三路归并排序及多路归并排序。本实例是二路归并排序，基本方法如下：
（1）将n个记录看成是n个长度为1的有序子表。
（2）将两两相邻的有序子表进行归并。
（3）重复执行步骤（2），直到归并成一个长度为n的有序表。
以下是归并排序法的C语言实现代码，包含合并和排序两个核心函数：
#include <stdio.h>
// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
int n1 = mid - left + 1;
int n2 = right - mid;
int L[n1], R[n2]; // 创建临时数组
// 复制数据到临时数组
for (int i = 0; i < n1; i++) L[i] = arr[left + i];
for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
// 合并临时数组到原数组
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) arr[k++] = L[i++];
else arr[k++] = R[j++];
}
// 复制剩余元素
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
}
// 归并排序主函数
void mergeSort(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2; // 避免溢出
mergeSort(arr, left, mid); // 递归排序左半部分
mergeSort(arr, mid + 1, right); // 递归排序右半部分
merge(arr, left, mid, right); // 合并有序数组
}
}
int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
printf("排序前数组：");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
mergeSort(arr, 0, n - 1);
printf("\n排序后数组：");
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
