合并排序

一.算法介绍
合并排序（Merge Sort）是一种高效的、基于比较的排序算法，采用分治策略进行工作。其基本思想是将数组分成两半，递归地对每半部分进行排序，然后将两个有序的半部分合并成一个有序序列。
二.算法步骤
合并排序可以分为两个主要步骤：
1.分解：将待排序的序列分解成尽可能小的子序列，直到每个子序列只包含一个元素（或空序列）。
2.合并：将子序列两两合并，形成新的有序序列，直到所有子序列合并成一个完全有序的序列。
三.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];

/* 复制数据到临时数组L[] 和 R[] */
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];

/* 合并临时数组回到arr[l..r]*/
int i, j, k;
i = 0; /* 初始化第一个和第二个子数组的初始索引 */
j = 0;
k = left; /* 初始索引的已排序子数组 */

while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}

/* 复制L[] 的剩余元素 */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}

/* 复制R[] 的剩余元素 */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}

/* l 是左边界索引， r 是右边界索引 */
void mergeSort(int arr[], int l, int r) {
if (l < r) {
// m是中间点
int m = l+(r-l)/2;

mergeSort(arr, l, m);
mergeSort(arr, m+1, r);

// 合并
merge(arr, l, m, r);
}
}

// 打印数组
void printArray(int A[], int size) {
int i;
for (i=0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}

int main() {
int arr[] = {12, 11, 13, 5, 6, 7};
int arr_size = sizeof(arr)/sizeof(arr[0]);

printf("Given array is \n");
printArray(arr, arr_size);

mergeSort(arr, 0, arr_size - 1);

printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;
}

四.时间复杂度
1.最好、最坏和平均时间复杂度均为 O(n log n)
2.空间复杂度为 O(n)
五.应用场景
合并排序适用于数据量大、对排序稳定性有要求的场景。由于其稳定的排序特性，以及较高的时间复杂度，它在处理大规模数据集时表现出色。
六.优缺点
1.优点：
①稳定排序：相同元素的相对位置不会改变。
②性能稳定：时间复杂度始终为 O(n log n)。
2.缺点：
①需要额外的存储空间：空间复杂度为 O(n)。
②递归调用可能带来一定的开销，尤其是在小数据集上。

合并排序是一种非常实用且高效的排序算法，在实际应用中具有广泛的适用性。