从IntroSort到MergeSort

Question

我知道，当使用类似于IntroSort的T[]调用时，比如Integer[] x；它将对数组进行排序，直到递归深度过大(在大多数实现中为0 )，然后它将切换到HeapSort。但是，当递归深度变为2log2n时，我试图调用一个修改的MergeSort。修改后的MergeSort只使用一个临时数组，该数组的大小是原始数组的一半，这只是为了节省一些时间和空间。无论如何，我基本上已经复制了所有的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 2(N)其中n是输入数

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

Answer 1

深度限制通常作为一个参数传递，其中包含一个条目/助手函数，该函数用初始值调用quicksort()作为深度限制。Wiki有一个例子，sort()是将深度限制传递给quicksort()的助手函数：

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

items.length是不会改变的。如果需要使用(右左)+1来获取当前子数组的长度。

请注意，对于快速排序，最坏的情况是长度m的子数组被分成两个子数组，一个长1，一个长m-1，除非不包括枢轴，在这种情况下，递归的最坏长度是1和m-2 (枢轴已经在适当的位置)。

合并排序只需对子数组进行排序，从&Tleft到&Tright。

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