这不是家庭作业，我没有钱上学，所以我在高速公路上的收费站轮班时自学（客户很少的长夜）
我试图通过首先思考来实现一个简单的"合并排序"，如果你喜欢的话，可以稍微伸展一下我的大脑进行一些实际的学习，然后查看我正在使用的手册上的解决方案："2008-08-21 |算法设计手册|Springer|Steven S.Skiena|ISBN-1848000693"。
我提出了一个解决方案，它使用数组作为缓冲区来实现"合并"步骤，我将其粘贴在下面。作者使用队列，所以我想知道：
- 是否应该使用队列
- 一种方法与另一种方法相比有什么优势？（很明显，他的方法会更好，因为他是一名顶级算法专家，而我是一名初学者，但我无法准确指出它的优点，请帮帮我）
- 他选择的权衡/假设是什么
这是我的代码（为了完整起见，我也包括了我对拆分功能的实现，但我认为我们在这里只是在审查merge步骤；顺便说一句，我不认为这是一篇代码审查文章，因为我的问题只针对一种方法，以及与另一种方法相比的性能）：
package exercises;
public class MergeSort {
private static void merge(int[] values, int leftStart, int midPoint,
int rightEnd) {
int intervalSize = rightEnd - leftStart;
int[] mergeSpace = new int[intervalSize];
int nowMerging = 0;
int pointLeft = leftStart;
int pointRight = midPoint;
do {
if (values[pointLeft] <= values[pointRight]) {
mergeSpace[nowMerging] = values[pointLeft];
pointLeft++;
} else {
mergeSpace[nowMerging] = values[pointRight];
pointRight++;
}
nowMerging++;
} while (pointLeft < midPoint && pointRight < rightEnd);
int fillFromPoint = pointLeft < midPoint ? pointLeft : pointRight;
System.arraycopy(values, fillFromPoint, mergeSpace, nowMerging,
intervalSize - nowMerging);
System.arraycopy(mergeSpace, 0, values, leftStart, intervalSize);
}
public static void mergeSort(int[] values) {
mergeSort(values, 0, values.length);
}
private static void mergeSort(int[] values, int start, int end) {
int intervalSize = end - start;
if (intervalSize < 2) {
return;
}
boolean isIntervalSizeEven = intervalSize % 2 == 0;
int splittingAdjustment = isIntervalSizeEven ? 0 : 1;
int halfSize = intervalSize / 2;
int leftStart = start;
int rightEnd = end;
int midPoint = start + halfSize + splittingAdjustment;
mergeSort(values, leftStart, midPoint);
mergeSort(values, midPoint, rightEnd);
merge(values, leftStart, midPoint, rightEnd);
}
}
这是教科书中的参考解决方案：（它在C中，所以我添加了标签）
merge(item_type s[], int low, int middle, int high)
{
int i; /* counter */
queue buffer1, buffer2; /* buffers to hold elements for merging */
init_queue(&buffer1);
init_queue(&buffer2);
for (i=low; i<=middle; i++) enqueue(&buffer1,s[i]);
for (i=middle+1; i<=high; i++) enqueue(&buffer2,s[i]);
i = low;
while (!(empty_queue(&buffer1) || empty_queue(&buffer2))) {
if (headq(&buffer1) <= headq(&buffer2))
s[i++] = dequeue(&buffer1);
else
s[i++] = dequeue(&buffer2);
}
while (!empty_queue(&buffer1)) s[i++] = dequeue(&buffer1);
while (!empty_queue(&buffer2)) s[i++] = dequeue(&buffer2);
}
抽象地说，队列只是一些支持入队、出队、peek和为空操作的对象。它可以用许多不同的方式实现（使用循环缓冲区、使用链表等）
从逻辑上讲，合并算法最容易用队列来描述。从两个包含要合并的值的队列开始，然后重复应用peek、is empty和对这些队列的出列操作，以重建单个排序序列。
在使用数组的实现中，您实际上是在做与使用队列相同的事情。您刚刚选择使用数组来实现这些队列。没有什么比使用队列更好或更糟糕的了。使用队列可以使合并算法的高级操作更加清晰，但可能会带来一些低效率（尽管在没有基准测试的情况下很难说）。使用数组可能会稍微高效一些（同样，您应该测试一下！），但可能会混淆算法的高级操作。从斯基纳的角度来看，使用队列可能会更好，因为它可以清楚地显示算法的高级细节。从您的角度来看，阵列可能会因为性能问题而变得更好。
希望这能有所帮助！
您担心的是次要的常量因素，这些因素在很大程度上取决于编译器的质量。考虑到您似乎对此感到担忧，数组就是您的朋友。下面是我的整数合并排序的C#实现，我认为它非常紧凑。[EDIT:修复了一个错误。]
如果您想在实践中做得更好，您需要类似于自然合并排序的东西，在这里，您只需合并相邻的非递减输入序列，而不是二次幂合并。这当然不比二的幂差，但当输入数据包含一些排序的序列（即，除了纯递减输入序列之外的任何序列）时，速度肯定更快。这是留给学生的练习。
int[] MSort(int[] src) {
var n = src.Length;
var from = (int[]) src.Clone();
var to = new int[n];
for (var span = 1; span < n; span += span) {
var i = 0;
for (var j = 0; j < n; j += span + span) {
var l = j;
var lend = Math.Min(l + span, n);
var r = lend;
var rend = Math.Min(r + span, n);
while (l < lend && r < rend) to[i++] = (from[l] <= from[r] ? from[l++] : from[r++]);
while (l < lend) to[i++] = from[l++];
while (r < rend) to[i++] = from[r++];
}
var tmp = from; from = to; to = tmp;
}
return from;
}