归并排序是一种基于分治思想的排序算法，核心逻辑是将原始数组不断拆分成更小的子数组，直到每个子数组只剩下一个元素，再将这些有序的子数组逐步合并成完整的有序数组。在C#中实现归并排序，需要分别处理数组拆分和子数组合并两个核心环节。
归并排序的核心原理
归并排序的执行过程可以分为两个主要阶段：
- 分（Divide）：将长度为n的数组拆分成两个长度为n/2的子数组，递归地对这两个子数组继续拆分，直到子数组的长度为1，此时每个子数组天然是有序的。
- 治（Conquer）：将两个有序的子数组合并成一个更大的有序数组，递归地执行合并操作，最终得到完整的有序数组。
合并两个有序数组的实现
合并操作是归并排序的核心，我们需要创建一个临时数组，依次比较两个有序子数组的元素，将较小的元素放入临时数组，直到其中一个子数组的所有元素都被放入临时数组，再把另一个子数组剩余的元素依次放入临时数组，最后将临时数组的内容复制回原数组的对应位置。
以下是合并两个有序子数组的C#代码实现：
// 合并两个有序子数组的方法
// arr: 原始数组
// left: 左子数组起始索引
// mid: 左子数组结束索引，右子数组起始索引为mid+1
// right: 右子数组结束索引
static void Merge(int[] arr, int left, int mid, int right)
{
// 计算两个子数组的长度
int leftLength = mid - left + 1;
int rightLength = right - mid;
// 创建临时数组存储两个子数组的元素
int[] leftTemp = new int[leftLength];
int[] rightTemp = new int[rightLength];
// 将原数组的左子数组元素复制到leftTemp
for (int i = 0; i < leftLength; i++)
{
leftTemp[i] = arr[left + i];
}
// 将原数组的右子数组元素复制到rightTemp
for (int j = 0; j < rightLength; j++)
{
rightTemp[j] = arr[mid + 1 + j];
}
// 合并两个临时数组到原数组
int p = 0; // leftTemp的索引
int q = 0; // rightTemp的索引
int k = left; // 原数组的填充索引
while (p < leftLength && q < rightLength)
{
if (leftTemp[p] <= rightTemp[q])
{
arr[k] = leftTemp[p];
p++;
}
else
{
arr[k] = rightTemp[q];
q++;
}
k++;
}
// 将leftTemp剩余的元素复制到原数组
while (p < leftLength)
{
arr[k] = leftTemp[p];
p++;
k++;
}
// 将rightTemp剩余的元素复制到原数组
while (q < rightLength)
{
arr[k] = rightTemp[q];
q++;
k++;
}
}
完整归并排序的C#实现
有了合并方法之后，我们只需要递归地拆分数组，再调用合并方法即可完成整个归并排序的实现：
// 归并排序的主方法，对外暴露调用入口
static 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);
}
}
// 测试代码示例
static void Main(string[] args)
{
int[] testArr = { 38, 27, 43, 3, 9, 82, 10 };
Console.WriteLine("排序前的数组：");
foreach (int num in testArr)
{
Console.Write(num + " ");
}
Console.WriteLine();
// 调用归并排序
MergeSort(testArr, 0, testArr.Length - 1);
Console.WriteLine("排序后的数组：");
foreach (int num in testArr)
{
Console.Write(num + " ");
}
}
归并排序的特性分析
时间复杂度
归并排序的时间复杂度稳定在O(n_log_n)，无论数组的初始顺序如何，都需要执行拆分和合并的完整流程，不会出现最坏情况的时间复杂度恶化。
空间复杂度
归并排序需要额外的临时数组来存储拆分后的子数组，空间复杂度为O(n)，相比快速排序等原地排序算法，空间开销更大。
稳定性
归并排序是稳定的排序算法，当两个元素相等时，合并过程中会优先保留左子数组的元素，不会改变相等元素的原始相对顺序。
适用场景
归并排序适合处理大规模数据的排序场景，尤其是当数据量较大、对排序稳定性有要求，且可以接受额外空间开销的情况。在C#中，如果需要实现稳定的O(n log n)排序，归并排序是一个可靠的选择。
C#归并排序merge_sort算法实现排序算法修改时间：2026-06-21 21:51:36