我一直在试图最近编码的递归版本后，了解非递归归并算法。我的AP本书并没有提供太多的信息或例子就这个话题，所以我希望有人能帮助我明确了一点东西。

I've been trying to understand the non-recursive MergeSort algorithm after recently coding the recursive version. My AP book doesn't provide too much info or examples on this topic so I was hoping someone could help me clear things up a bit.

什么我的书由以下意思：以非递归归并方法我们将列表分为两个大小相等的部分和排序的每个与选择排序，然后使用一种算法，将要讨论的合并两个B部分。

What does my book mean by the following: "In a non-recursive mergeSort method. We divide the list into two equal-sized parts and sort each with the selection sort, then merge the two using an algorithm to be discussed in part B."

难道人们总是划分阵列分为两部分的非递归归并排序法（然后相应地对它们进行排序），还是有类似的递归版本情况下，你不断分裂，直至到达array.length 2或1 ？

Does one always divide an array into two pieces in a non-recursive mergeSort method (and then sort them accordingly), or are there cases like the recursive version where you keep dividing until you get to array.length of 2 or 1?

图书code：

void mergeSort (ArrayList <Integer> A, int first, int last){
   int mid;

   mid = (first + last) / 2;
   selectionSort (A, first, mid);
   selectionSort (A, mid+1, last);
   merge (A, first, mid, last);
 }

如果你总是分割数组2，然后排序是怎么这有效吗？如果您的数组包含上千个值会​​发生什么。 。 。不会递归会更好，因为它在更小的碎片进行排序的值？

If you always divide the array into 2 and then sort how is this efficient? What happens if your array contains thousands of values . . . wouldn't recursive be better off as it sorts the values in smaller pieces?

图书展示：

推荐答案

从我的理解是什么书的意思是，你可以通过选择排序使用合并划分阵列中的一半，排序每个阵列，然后合并这两个半算法（这将是相同递归归并）。它可能只需要显示合并是如何工作的。

From my understanding what the book means is that you can divide the array in half, sort each array using selection sort, and then merge these two halves using the merge algorithm (which would be the same as for recursive mergesort). It may only want to show how the merging works.

但是这个实现是不会一个合并。这是渐进的效率将是远远糟糕比归并排序的为O（n的log（n））来选择排序是O（n ^ 2）。

However this implementation is NOT a mergesort. It's asymptotic efficiency is going to be far worse than mergesort's O(n log(n)) as selection sort is O(n^2).

但它是可以做到一个合并无需使用递归 - 你可以使用迭代。见实施这里。

But it is possible to do a mergesort without the use of recursion - you could use iterations. See the implementation here.