一、算法简介
归并排序（Merge Sort）是一种基于分治思想的排序算法，它将待排序的数组不断一分为二，直到划分成单个元素为止，然后再将小的子数组逐步合并成较大的有序数组，最终完成整个数组的排序。
归并排序的基本思想是先递归地将数组一分为二，然后对两个子数组进行排序，最后将排序好的子数组合并成一个有序的数组。在合并的过程中，通过比较两个子数组中的元素，按从小到大（或从大到小）的顺序放入一个临时数组中，直至将两个子数组完全合并为止。
归并排序的实现通过递归和迭代两种方式都可以完成。其中，递归方式的实现较简单，而迭代方式则需要使用循环和辅助空间来实现合并操作。
归并排序的时间复杂度为O(nlogn)，具有稳定性，即相等元素的顺序在排序后保持不变。它是一种效率较高的排序算法，特别适用于大规模数据的排序。
二、算法实现
下面是归并排序在C#中的一个示例实现：
public static void MergeSort(int[] array) { int n = array.Length; if (n < 2) return; int mid = n / 2; int[] left = new int[mid]; int[] right = new int[n - mid]; // 将数组分成左右两个子数组 for (int i = 0; i < mid; i++) { left[i] = array[i]; } for (int i = mid; i < n; i++) { right[i - mid] = array[i]; } // 递归地对左右子数组进行排序 MergeSort(left); MergeSort(right); // 合并已排序的左右子数组 Merge(left, right, array); } private static void Merge(int[] left, int[] right, int[] array) { int leftLength = left.Length; int rightLength = right.Length; int i = 0, j = 0, k = 0; while (i < leftLength && j < rightLength) { if (left[i] <= right[j]) { array[k] = left[i]; i++; } else { array[k] = right[j]; j++; } k++; } // 如果左子数组还有未处理的元素，将其放入合并后的数组中 while (i < leftLength) { array[k] = left[i]; i++; k++; } // 如果右子数组还有未处理的元素，将其放入合并后的数组中 while (j < rightLength) { array[k] = right[j]; j++; k++; } }
调用示例：
int[] array = { 12, 11, 13, 5, 6, 7 }; MergeSort(array); Console.WriteLine("排序后的数组："); foreach (int element in array) { Console.Write(element + " "); }
以上是一个简单的归并排序实现示例。在该实现中，使用递归方式对数组进行划分和排序，并通过合并操作将已排序的子数组合并为一个有序的数组。注意，在合并过程中需要创建临时数组来辅助合并操作。请注意，在实际应用中，还可以进行一些优化措施，如改进合并操作、避免创建额外的临时数组等。
