算法Java mergesort，“合并”步骤应该对队列或数组执行吗？

Question

这不是家庭作业，我没有钱上学，所以我在高速公路上的收费站轮班工作时自学（长夜很少有顾客）

我试图通过思考来实现一个简单的“合并排序”，首先，如果你愿意进行一些实际的学习，我会稍微伸展一下大脑，然后查看我正在使用的手册上的解决方案：“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);
}

Answer 1

从抽象意义上讲，队列只是一些支持排队、出列、查看操作的对象，并且是空操作。它可以通过许多不同的方式实现（使用循环缓冲区、使用链表等）

从逻辑上讲，合并算法最容易用队列来描述。首先是两个队列，其中包含要合并在一起的值，然后重复应用peek、is empty和对这些队列的出列操作，以重建单个排序序列

在使用阵列的实现中，您实际上做的是与使用队列相同的事情。您刚刚选择使用数组实现这些队列。没有什么比使用队列更好或更糟的了。使用队列可以使合并算法的高级操作更清晰，但可能会带来一些低效（尽管在没有基准测试的情况下很难确定）。使用数组可能会稍微高效一些（同样，您应该对此进行测试！），但可能会掩盖算法的高级操作。从斯基纳的角度来看，使用队列可能更好，因为它可以让算法的高级细节变得清晰。从您的角度来看，由于性能问题，阵列可能会更好

希望这有帮助

Answer 2

您担心的是次要的常量因素，这在很大程度上取决于编译器的质量。考虑到你似乎对此很担心，数组是你的朋友。下面是我对整数合并排序的C#实现，我认为，这是你能得到的最紧密的。[编辑：修正了小号。]

如果你想在实践中做得更好，你需要像自然合并排序这样的东西，在这里，你不需要以二的幂合并，只需要合并相邻的非递减输入序列。这当然不比二的幂差，但当输入数据包含一些排序序列（即，除纯降序输入序列外的任何序列）时，速度肯定更快。这是留给学生的练习

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;
}