为什么在大多数在线实现中，intro sort只使用一个递归？

Question

我在读介绍排序的文章。我理解它的大部分，但我不能理解为什么大多数实现倾向于使用一个递归来实现快速排序部分。快速排序的标准实现使用两个递归进行快速排序。

Intro sort, main logic:
  private static void introsort_loop (int[] a, int lo, int hi, int depth_limit)
    {
      while (hi-lo > size_threshold)
      {
        if (depth_limit == 0)
        {
          heapsort(a, lo, hi);
          return;
        }
        depth_limit=depth_limit-1;
        int p=partition(a, lo, hi, medianof3(a, lo, lo+((hi-lo)/2)+1, hi-1));
        introsort_loop(a, p, hi, depth_limit);
        hi=p;
      }
      insertionsort(a, lo, hi);
    }

在这里，我尝试将其修改为：

  private static void introsort_loop (int[] a, int lo, int hi, int depth_limit)
    {
      if (hi-lo > size_threshold)
      {
        if (depth_limit == 0)
        {
          heapsort(a, lo, hi);
          return;
        }
        depth_limit=depth_limit-1;
        int p=partition(a, lo, hi, medianof3(a, lo, lo+((hi-lo)/2)+1, hi-1));
        introsort_loop(a, p + 1, hi, depth_limit);
        introsort_loop(a, lo , p-1 , depth_limit);
      }
      insertionsort(a, lo, hi);
    }

我做了两个修改，一个是我现在使用了两个递归，第二个我跳过了递归的pivot元素，因为它已经在正确的位置了。

无论有没有我的修改，程序似乎都运行得很好。但我想知道为什么他们在大多数在线实现中使用单递归。

Answer 1

快速排序的许多实现实际上使用单个递归和while循环作为节省空间和时间的技巧。

从数学上讲，快速排序算法看起来像这样：

 Partition elements.
 Quicksort(elements less than pivot)
 Quicksort(elements greater than pivot)

如果您注意到，在两个递归调用返回后，没有需要执行的代码。

现在，考虑一下如果您直接将此伪代码转换为真实代码会发生什么。最初调用quicksort时的原始堆栈帧将一直存在，直到对quicksort的两个子调用都返回为止。这意味着堆栈帧的内存将一直存在，直到整个算法运行完毕，这会占用大量空间。此外，如果快速排序遇到退化情况(在introsort中是不可能的，但请稍等片刻)，那么您将最终触发堆栈溢出。

解决这个问题的一个聪明的方法是认识到上面描述的快速排序实际上适用于tail call elimination。也就是说，该实现可以只覆盖初始调用的参数，然后在while循环中重用堆栈帧中的空间，而不是对快速排序进行第二次调用。这最终大大减少了空间使用，并消除了递归调用，而递归调用(虽然不是非常昂贵)通常比while循环的成本更高。通常，实现将在数组的两半中较小的一半上启动递归调用，并使用while循环来处理较大的调用，这保证了空间使用率为O(log )，即使您得到了退化的情况。

上面列出的introsort实现看起来只是为了适应introsort而不是quicksort。使用一次递归调用而不是两次递归调用并不意味着算法没有使用快速排序，而只是意味着它使用了标准的快速排序优化技术。