C语言实现归并排序详解及优化250

归并排序 (Mergesort) 是一种高效且稳定的排序算法，它采用分治策略，将待排序序列递归地分割成更小的子序列，直到每个子序列只包含一个元素（此时认为已排序），然后将这些子序列合并成更大的已排序序列。其时间复杂度始终为 O(n log n)，空间复杂度为 O(n)，适用于各种规模的数据排序。

本文将详细介绍 C 语言中归并排序的实现，包括递归实现和迭代实现，并探讨一些优化策略，以提高算法的性能。

递归实现

递归实现是归并排序最直观和易于理解的实现方式。其核心思想是：首先将待排序序列分成两半，然后递归地对这两半进行排序，最后将两个已排序的子序列合并成一个已排序的序列。以下是一个 C 语言的递归实现：```c
#include
#include
// 合并两个已排序的子数组
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// 创建临时数组
int L[n1], R[n2];
// 复制数据到临时数组
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
// 合并临时数组到arr[]
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i]