从 IntroSort 到 MergeSort

Question

我知道当使用 T[] 之类的东西调用 IntroSort 时，说 Integer[] x；它会对数组进行排序，直到递归深度太多（在大多数实现中变为 0），然后它会切换到 HeapSort。但是，当递归深度变为 2log2n 时，我试图调用修改后的 MergeSort。修改后的 MergeSort 只使用了一个临时数组，大小是原数组的一半，只是为了节省一点时间和space。无论如何，我基本上已经复制了所有 QuickSort，除了我在它递归调用之前添加了一个 depth_limit 检查。

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

我认为这会奏效，因为我相信

depth_limit = 2*log2(n) 其中 n 是输入的数量

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

Answer 1

深度限制通常作为参数传递，带有一个入口/辅助函数，该函数使用深度限制的初始值调用 quicksort()。 Wiki 有一个例子，sort() 是将深度限制传递给 quicksort() 的辅助函数：

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

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

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

合并排序只需要将子数组从 &T[left] 排序到 &T[right]。

通过对原始数组的两半进行排序，然后将数组的前半部分复制到工作数组，自上而下或自下而上的合并排序可以使用原始数组大小的 1/2 的工作数组，然后将工作数组和原始数组的后半部分最终合并回原始数组（对于奇数大小的原始数组，工作数组和 "first" 一半数组大小为 n/2 + 1）。

从 IntroSort 到 MergeSort

Going from IntroSort to a MergeSort

java

sorting

recursion

quicksort