java - 从 IntroSort 转到 MergeSort

Question

我知道当使用 T[] 之类的东西调用 IntroSort 时，请说 Integer[] x;它将对数组进行排序，直到递归深度太多(在大多数实现中为 0)，然后它将切换到 HeapSort。但是，当递归深度变为 2log2n 时，我尝试调用修改后的 MergeSort。修改后的MergeSort只使用了原数组一半大小的临时数组，只是为了节省一点时间和空间。不管怎样，我基本上已经复制了所有的 QuickSort，除了在递归调用之前添加了深度限制检查。

private void quicksort(T[] items, int left, int right) {
    int depth_limit = (int) (2*Math.log(items.length));
    if(depth_limit == 0)
    {
      mergesorter.sort(items, left, right);
      return;
    }
    int pivotindex = findpivot(items, left, right);

    // curr will be the final position of the pivot item.
    int curr = partition(items, left, right, pivotindex);

    if ((curr - left) > 1) {
      quicksort(items, left, curr - 1); // Sort left partition
    }
    if ((right - curr) > 1) {
      quicksort(items, curr + 1, right); // Sort right partition
    }
  }

我认为这会起作用，因为我相信

深度限制 = 2*log2(n)，其中 n 是输入数量

所以我的问题是，我在哪里检查递归深度以切换到合并排序以及我是否正确计算了我的深度？

Answer 1

深度限制通常作为参数传递，并带有一个条目/辅助函数，该函数使用深度限制的初始值调用快速排序()。 Wiki 有一个示例，sort() 是将深度限制传递给 Quicksort() 的辅助函数:

http://en.wikipedia.org/wiki/Introsort

items.length 不会改变。如果需要，使用 (right - left)+1 获取当前子数组的长度。

请注意，快速排序的最坏情况是长度为 m 的子数组被分成两个子数组，一个长度为 1，一个长度为 m-1，除非排除主元，在这种情况下是最坏情况递归的长度是 1 和 m-2(枢轴已经在正确的位置)。

合并排序只需将子数组从 &T[左] 排序到 &T[右]。

自上而下或自下而上的合并排序都可以使用原始数组大小 1/2 的工作数组，方法是对原始数组的两半进行排序，然后将数组的前半部分复制到工作数组，然后执行以下操作将工作数组和原始数组的后半部分最终合并回原始数组(对于奇数大小的原始数组，工作数组和“前”半数组大小为 n/2 + 1)。