C＃合并排序性能
只是一个简单的说明，这不是功课。 我只是想弄清楚我的算法。 我在C＃中使用MergeSort，我编写了一个可以根据generics进行排序的递归方法：
class SortAlgorithms { public T[] MergeSort (T[] unsortedArray) where T : System.IComparable { T[] left, right; int middle = unsortedArray.Length / 2; left = new T[middle]; right = new T[unsortedArray.Length - middle]; if (unsortedArray.Length <= 1) return unsortedArray; for (int i = 0; i < middle; i++) { left[i] = unsortedArray[i]; } for (int i = middle; i < unsortedArray.Length; i++) { right[i - middle] = unsortedArray[i]; } left = MergeSort(left); right = MergeSort(right); return Merge(left, right); } private T[] Merge (T[] left, T[] right) where T : System.IComparable { T[] result = new T[left.Length + right.Length]; int currentElement = 0; while (left.Length > 0 || right.Length > 0) { if (left.Length > 0 && right.Length > 0) { if (left[0].CompareTo(right[0]) 0) { result[currentElement] = left[0]; left = left.Skip(1).ToArray(); currentElement++; } else if (right.Length > 0) { result[currentElement] = right[0]; right = right.Skip(1).ToArray(); currentElement++; } } return result; } } 这有效，但速度很慢。 我已经使用System.Diagnostic.StopWatch来检查Array.Sort（它使用QuickSort算法）的性能来与我的MergeSort进行比较，差异是如此显着我想知道我是否实现了这个错误。 任何意见？
我不是C＃程序员，但问题可能是使用像这样的语句吗？
left = left.Skip(1).ToArray();
这可能以强制底层数组的深层副本的方式实现。 如果是这样，这会将合并的性能从O（n）降低到O（n 2 ），立即将生成的合并排序的性能从O（n log n）降低到O（n 2 ）。
（这是因为重复发生变化
T（1）= O（1）
T（n）≤2T（n / 2）+ O（n）
其解决方案T（n）= O（n log n），to
T（1）= O（1）
T（n）≤2T（n / 2）+ O（n 2 ）
它有解T（n）= O（n 2 ）。）
您不断以中间数组的forms分配内存。 想一想重用原始数组的方向。
正如其他两个答案所说，你正在创造新的arrays，花费大量的时间和内存（我猜，你的大部分时间和几乎所有的内存使用）。
再说一遍，我要补充一点，其他所有相等的递归往往比迭代慢，并且使用更多的堆栈空间（甚至可能导致溢出有足够大的问题，迭代不会）。
然而。 Merge-sort非常适合multithreading方法，因为您可以让不同的线程处理第一批分区的不同部分。
因此，如果我正在玩这个，我接下来的两个实验将是：
- 对于分区的第一位，而不是递归地调用
MergeSort，我会启动一个新线程，直到每个核心运行一个线程为止（无论我是应该在每个物理核心还是虚拟核心的情况下进行超线程） ，本身就是我要试验的东西）。 - 完成后，我会尝试重写递归方法，以便在没有递归调用的情况下执行相同的操作。
在处理了ToArray()问题之后，看看multithreading方法如何首先将工作分成最佳数量的内核，然后让每个内核迭代地完成其工作，确实非常有趣。
首先，这里是一个关于类似问题的简化解决方案的链接： Java mergesort，是否应该使用队列或数组完成“合并”步骤？
您的解决方案很慢，因为您反复分配新的子arrays。 内存分配比大多数其他操作更昂贵（您有分配成本，收集成本和缓存局部性丢失）。 通常情况下这不是问题，但如果您正在尝试编写严格的排序例程，那么这很重要。 对于合并排序，您只需要一个目标数组和一个临时数组。
分叉线程并行仍然比这更昂贵。 所以除非你有大量的数据要排序，否则不要分叉。
正如我在上面的答案中提到的，加速合并排序的一种方法是利用输入数组中的现有顺序。