libstdc++ std：：inplace_merge （__merge_without_buffer） 的时空复杂度

问：

libstdc++ std：：inplace_merge调用的__merge_without_buffer实现的算法的时间和空间复杂度是多少？更具体地说，我对这些感兴趣：

• 递归深度的上限。是 <= 2 * ceil（log2（n）） 吗？

• 比较次数的上限。是 <= 2 * ceil（log2（n）） * n 吗？

• 掉期次数的上限。是 <= 2 * ceil（log2（n）） * n 吗？

理想情况下，该算法是一篇著名论文中描述的著名算法，并且该论文包含这些上限作为证明。但是，libstdc++ 源代码未指定任何源代码。

对于上面的 <= ... 问题，我凭直觉得到了这些公式猜想，运行了 C 程序，对许多输入进行了计数，并检查了这些输入的上限。但是，在一般情况下，我无法证明我的任何猜想。对于递归深度公式，将常数从 2 更改为 1.5 会使其为 false，我发现了一些反例。

请注意，我对 O（...） 类不感兴趣，但我想要一个实际的上限，具有特定的常量（希望是 2 或更少）。我还需要上限公式的证明。引文就足以作为证据。

根据实现的注释和文档，我认为比较次数和交换次数都是 O（log2（n） * n）。但是，没有证据，这不是上限公式，并且缺少递归深度的公式。

很容易证明，在常规（非就地）合并算法中，没有递归，比较次数为 <= n - 1，没有交换，副本数为 n。但是，我对就地合并算法特别感兴趣。

上面的 n 是输入/输出数组中的元素总数 （== n1 + n2 == len1 + len2 == __len1 + __len2）。

在计算 rotate 函数使用的交换次数时，请使用比传递给 rotate 函数的元素总数少 1 作为上限。

以下是此算法的一些实现：

• C++：libstdc++ 中的__merge_without_buffer函数，由 std：：inplace_merge 调用。
• Java：合并，在 Java 中重新实现 C++ __merge_without_buffer 函数。
• C：ip_merge_，在 C 中重新实现 C++ __merge_without_buffer 函数。

请注意，上述实现在递归深度、比较次数和交换次数（如上定义）方面是等效的。

这篇博文介绍了一种不同的就地合并排序。该算法仅交换相同大小的相邻内存区域。

实用就地合并一文（也在此处的 C++ 代码注释中进行了解释）解释了一种不同的就地合并算法。

为了完整起见，我在这里复制了 C 实现：

#define SWAP(type, a, b) \
    do { type t=(a);(a)=(b);(b)=t; } while (0)

static void reverse_(int* a, int* b)
{
    for ( --b; a < b; a++, b-- )
       SWAP(int, *a, *b);
}
static int* rotate_(int* a, int* b, int* c)
/* swap the sequence [a,b) with [b,c). */
{
    if (a != b && b != c)
     {
       reverse_(a, b);
       reverse_(b, c);
       reverse_(a, c);
     }
    return a + (c - b);
}

static int* lower_bound_(int* a, int* b, const int key)
/* find first element not less than @p key in sorted sequence or end of
 * sequence (@p b) if not found. */
{
    int i;
    for ( i = b-a; i != 0; i /= 2 )
     {
       int* mid = a + i/2;
       if (*mid < key)
          a = mid + 1, i--;
     }
    return a;
}
static int* upper_bound_(int* a, int* b, const int key)
/* find first element greater than @p key in sorted sequence or end of
 * sequence (@p b) if not found. */
{
    int i;
    for ( i = b-a; i != 0; i /= 2 )
     {
       int* mid = a + i/2;
       if (*mid <= key)
          a = mid + 1, i--;
     }
    return a;
}

static void ip_merge_(int* a, int* b, int* c)
/* inplace merge. */
{
    int n1 = b - a;
    int n2 = c - b;

    if (n1 == 0 || n2 == 0)
       return;
    if (n1 == 1 && n2 == 1)
     {
       if (*b < *a)
          SWAP(int, *a, *b);
     }
    else
     {
       int* p, * q;

       if (n1 <= n2)
          p = upper_bound_(a, b, *(q = b+n2/2));
       else
          q = lower_bound_(b, c, *(p = a+n1/2));
       b = rotate_(p, b, q);

       ip_merge_(a, p, b);
       ip_merge_(b, q, c);
     }
}