归并排序（Merge
Sort）是一种高效的排序算法，它采用了分治法（Divide
and
Conquer）的思想。归并排序的基本步骤如下：
1.分解：将原始数组不断分割成两个半，直到每个子数组只包含一个元素为止。
2.解决：对于只有两个元素的子数组，它们已经是有序的。
3.合并：将两个有序子数组合并成一个新的有序数组。
以下是一个简单的归并排序算法的C语言实现：
```c
include
void
merge(int
arr[],
int
left,
int
mid,
int
right)
{
int
i,
j,
k;
int
n1
=
mid
left
+
1;
int
n2
=
right
mid;
int
L[n1],
R[n2];
for
(i
=
0;
i
<
n1;
i++)
L[i]
=
arr[left
+
i];
for
(j
=
0;
j
<
n2;
j++)
R[j]
=
arr[mid
+
1
+
j];
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++;
}
while
(i
<
n1)
{
arr[k]
=
L[i];
i++;
k++;
}
while
(j
<
n2)
{
arr[k]
=
R[j];
j++;
k++;
}
}
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[]
=
{4,
3,
7,
2,
9,
5};
int
n
=
sizeof(arr)
/
sizeof(arr[0]);
mergeSort(arr,
0,
n
1);
printf("Sorted
array:
\n");
for
(int
i
=
0;
i
<
n;
i++)
printf("%d
",
arr[i]);
printf("\n");
return
0;
}
```
在这个代码中，`merge`
函数负责合并两个已排序的子数组，而
`mergeSort`
函数则递归地将整个数组分解并排序。归并排序的时间复杂度为
O(n
log
n)，其中
n
是数组中元素的数量。因为归并排序是稳定的，所以它适用于对大量数据进行排序。
