c++ - 这是一种什么样的排序，它的运行时间是多少？

Question

我想知道下面的排序是什么样的排序，大 O 表示法的运行时间是多少？我的朋友在没有任何算法知识的情况下编写了这个排序函数，现在我们正在争论它的速度/内存效率如何。所以请你帮我们分析一下。

void sort(int* a, int size)
{
    if (size <= 1) return;
    else if (size == 2)
    {
        if (a[0] > a[1])
            swap (a[0], a[1]);
        return;
    }
    else
    {
        int i = size / 2;
        sort(a, i);
        sort(a+i, size - i);
        int j = 0, k = i ;
        while (k < size && j < k)
        {
            if (a[j] > a[k])
            {
                int temp = k;
                while (temp > j)
                {
                    swap(a[temp - 1], a[temp]);
                    temp--;
                }
                k++;
            }
            j++;
        }
    }
}

谢谢 ：）

Answer 1

这基本上是合并排序，但有一个 ^2 就地合并步骤。如果你做标准数学，就像分析归并排序一样，你会发现它有 n^2 的运行时间。为此，您需要求解的相关方程是f(n) = n^2 + 2f(n/2)。