mergesort在c#中需手动实现，因.net未提供内置方法，array.sort()等使用introsort而非归并排序；其实现要点包括分治策略、防溢出中点计算、临时数组合并及处理剩余元素。
MergeSort 在 C# 中必须手动实现，.NET 框架不提供内置的 MergeSort 方法；它不是 List<t>.Sort()</t> 或 Array.Sort() 的底层算法（它们用的是 introsort）。
为什么不能直接调用现成的 MergeSort
.NET 的排序 API 默认不暴露归并排序接口。即使你传入自定义 IComparer<t></t>，Array.Sort() 仍走 introsort（快排+堆排+插排混合），稳定性和分治结构都不满足归并排序需求。需要手写才能控制合并逻辑、保证稳定性、或用于教学/特殊场景（如外部排序、链表排序）。
基础递归版 MergeSort 实现要点
核心是「分而治之 + 合并有序子数组」。常见错误是索引越界或合并时遗漏元素。
- 递归终止条件必须是
left >= right（单个或零元素），不是left == right - 中点计算用
int mid = left + (right - left) / 2，避免left + right溢出（尤其大数组） - 合并时需额外空间：新建临时数组或使用原数组辅助区，不能边合并边覆盖原数据
- 合并循环要处理「左/右子数组剩余未拷贝元素」——这是最容易漏掉的 bug 点
示例片段（就地排序，返回新数组）：
static int[] MergeSort(int[] arr) {
if (arr.Length <= 1) return arr;
int mid = arr.Length / 2;
var left = MergeSort(arr[..mid]);
var right = MergeSort(arr[mid..]);
return Merge(left, right);
}
<p>static int[] Merge(int[] left, int[] right) {
int[] result = new int[left.Length + right.Length];
int i = 0, j = 0, k = 0;
while (i < left.Length && j < right.Length) {
result[k++] = left[i] <= right[j] ? left[i++] : right[j++];
}
while (i < left.Length) result[k++] = left[i++];
while (j < right.Length) result[k++] = right[j++];
return result;
}优化：避免频繁数组分配的 Bottom-up 迭代版
递归版每次 new int[] 开销大，且有栈溢出风险（深度 ~log₂n）。迭代版用固定辅助数组 + 自底向上合并，更适合大数据量。
- 先申请一个与原数组等长的
temp数组复用 - 用
width控制当前子数组长度（1 → 2 → 4 → …） - 每轮对相邻两个
width长度的块合并，注意边界检查：mid = Math.Min(i + width - 1, n - 1) - 合并结果先写入
temp，再Array.Copy回原数组（或双缓冲交替）
关键参数差异：Array.Sort() 是 in-place 且不稳定；你的 MergeSort 若想 in-place 合并，复杂度会升到 O(n²)，不推荐——接受 O(n) 额外空间才是标准做法。
用在 List 或自定义类型时要注意什么
泛型版本必须支持比较：要么约束为 IComparable<t></t>，要么接收 Comparison<t></t> 或 IComparer<t></t> 参数。
- 别直接改
List<t></t>内部数组（list.ToArray()是安全副本） - 若 T 是引用类型，排序只重排引用，不影响对象本身
- 稳定性依赖合并时的「comparer.Compare(a, b) ，不是
，否则破坏稳定性 - 对大对象（如
string或自定义类），避免在比较器里做重操作（如正则匹配）
性能上，MergeSort 始终是 O(n log n)，但常数因子比 Array.Sort() 大约 2–3 倍；仅在需要稳定排序、链表排序、或数据无法随机访问时才值得替换。
真正难的不是写出来，而是确保合并循环收尾逻辑全覆盖，以及泛型比较器和边界条件在各种输入下不崩——多用空数组、单元素、已排序、逆序这四类 case 测一遍。
