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 测一遍。
