libstdc++ std::inplace_merge的__merge_without_buffer算法复杂度问询

核心问题 #

我需要明确libstdc++中std::inplace_merge调用的__merge_without_buffer实现的时间与空间复杂度，尤其关注以下带具体常数的实际上限（而非大O复杂度类）：

• 递归深度的上限是否≤2*ceil(log₂(n))？
• 比较次数的上限是否≤2*ceil(log₂(n))*n？
• 交换次数的上限是否≤2*ceil(log₂(n))*n？

注：此处n为输入输出数组的总元素数（即n = n₁ + n₂，n₁、n₂为待合并的两个有序子数组长度）。计算rotate函数的交换次数时，以传入元素总数减1作为上限。

背景说明 #

我通过直觉和带计数的C程序测试多个输入，得出了上述猜想，但无法证明通用情况——例如将递归深度公式中的常数从2改为1.5时，存在反例。libstdc++源码未注明该算法的论文来源，但我推测它属于经典原地归并算法，理想情况下相关论文会包含上述上限的证明。

目前已知该算法的比较和交换次数均为O(log₂(n)*n)，但缺少具体上限公式和递归深度的严谨证明。需注意：我仅关注原地归并算法，常规非原地归并算法无递归、比较次数≤n-1、无交换但有n次复制，不在讨论范围内。

等价实现说明 #

以下几种实现的递归深度、比较次数、交换次数完全等价：

• C++：libstdc++中的__merge_without_buffer函数，被std::inplace_merge调用
• Java：__merge_without_buffer的Java重实现
• C：ip_merge_函数，__merge_without_buffer的C简化重实现
• C：ip_mergesort函数，基于上述ip_merge_的原地归并排序实现，接口兼容qsort(3)

另有《Practical In-Place Merging》一文及相关代码注释介绍了另一种原地归并算法，与本文讨论的算法逻辑不同。

附：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)
/* 交换序列 [a,b) 和 [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)
/* 在有序序列中找到第一个不小于key的元素，若不存在则返回b */
{
    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)
/* 在有序序列中找到第一个大于key的元素，若不存在则返回b */
{
    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)
/* 原地归并 */
{
    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);
     }
}

内容的提问来源于Stack Exchange，提问作者pts