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 点

示例片段（就地排序，返回新数组）：

优化：避免频繁数组分配的 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 测一遍。