java - 看不懂非递归MergeSort算法

Question

在最近对递归版本进行编码之后，我一直在尝试理解非递归 MergeSort 算法。我的 AP 书没有提供太多关于这个主题的信息或示例，所以我希望有人能帮我澄清一下。

我的书中的以下内容是什么意思:“在非递归 mergeSort 方法中。我们将列表分成两个大小相等的部分，并使用选择排序对每个部分进行排序，然后使用将在 中讨论的算法合并这两个部分B 部分。”

是否总是在非递归 mergeSort 方法中将数组分成两部分(然后相应地对它们进行排序)，或者是否存在像递归版本这样的情况，在这种情况下，您会一直划分直到 array.length 为 2 或 1 ？

图书代码:

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份，然后排序，效率如何？如果您的数组包含数千个值，会发生什么情况。 . .递归不是更好吗，因为它将值分成更小的部分？

图书示范:

Answer 1

根据我的理解，这本书的意思是您可以将数组分成两半，使用选择排序对每个数组进行排序，然后使用合并算法合并这两半(这与递归归并排序相同)。它可能只想显示合并的工作原理。

但是这个实现不是归并排序。它的渐近效率将远差比归并排序的 O(n log(n)) 因为选择排序是 O(n^2)。

但是可以在不使用递归的情况下进行归并排序——您可以使用迭代。查看实现 here .