Java mergesort，是否应该使用队列或数组完成“合并”步骤？
这不是家庭作业，我没有钱上学，所以我在高速公路上的收费站换class时教我自己（很少有顾客的长夜）
我试图通过首先考虑实现一个简单的“mergesort”，如果你喜欢一些实际的学习， 那么我的大脑会稍微伸展一下， 然后看看我正在使用的手册上的解决方案：“2008-08-21 |算法设计手册| Springer |作者：Steven S. Skiena | ISBN-1848000693“。
我想出了一个解决方案，它使用数组作为缓冲区来实现“合并”步骤，我将其粘贴到下面。 作者使用队列，所以我想知道：
- 应该使用队列吗？
- 一种方法对另一种方法有什么好处？ （显然他的方法会更好，因为他是一个顶级的算法，我是一个初学者，但我不能完全指出它的优点，请帮助我）
- 支配他选择的权衡/假设是什么？
这是我的代码（为了完整起见我也包括我的分裂function的实现，但我认为我们只是在这里审查merge步骤;我不相信这是一个代码审查post，因为我的问题是仅针对一种方法以及与另一种方法相比的性能：
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); }
抽象地说，队列只是支持enqueue，dequeue，peek和is-empty操作的对象。 它可以通过许多不同的方式实现（使用循环缓冲区，使用链接列表等）
从逻辑上讲，合并算法最容易用队列来描述。 首先，将两个队列保持合并在一起，然后对这些队列重复应用peek，is-empty和dequeue操作以重建单个排序序列。
在使用数组的实现中，您实际上就像使用队列一样。 您刚刚选择使用数组实现这些队列。 与使用队列相比，不一定“更好”或“更差”。 使用队列使得合并算法的高级操作更加清晰，但可能会引入一些低效率（尽管如果没有基准测试很难确定）。 使用数组可能会稍微更有效（同样，你应该测试它！），但可能会模糊算法的高级操作。 从Skienna的角度来看，使用队列可能会更好，因为它使算法的高级细节变得清晰。 从您的角度来看，由于性能问题，数组可能会更好。
希望这可以帮助！
你担心微小的常数因素，这些因素在很大程度上取决于编译器的质量。 鉴于你似乎对此感到担心，数组就是你的朋友。 下面是整数合并排序的C＃实现，我认为它接近于你能得到的最紧密。 [编辑：修正了一个小程序。]
如果你想在实践中做得更好，你需要像自然合并排序这样的东西，而不是合并为2的幂，你只需合并输入的相邻非递减序列。 这肯定不比2的幂更差，但是当输入数据包含一些排序的序列（即除了纯粹下降的输入序列之外的任何东西）时肯定更快。 那是留给学生的练习。
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; }