为什么排序算法的时间上限被锁死在了O(nlogn)

November 23, 2025 | 算法时空 | 10 min read

基于比较的排序算法

实现n个不同元素的重排序，即在 $n!$ 种全排列组合中找到从小到大，或从大到小排列的那一种情况。而常见排序算法的比较/交换的过程就是逐渐让数组变得有序的过程。

而我们知道，常见排序算法例如比较排序、归并排序，他们的时间复杂度在平均情况下均为 $O(n\log_2 n)$ 。可是是什么限制了这类排序算法的时间上限就是 $O(n\log_2 n)$ ？或者说，我们是不是可以找到比他更快的排序算法，而只是我们目前为止并没有找到。

这个问题让我很困惑，经过对各种资料的整理，我初步弄明白了这件事情：实际上，这时基于“比较”的排序算法的固有上限。也就是说，在这种思路下，无论聪明的程序员们想出怎样优雅的排序过程，他们在本质上是等价的，而排序过程的平均时间复杂度都不会超出 $O(n\log_2 n)$ 。

让我们先回到代码本身， $O(n\log_2 n)$ 到底是怎么来的呢？为什么这里出现了一个一个以2为底的对数呢？下面我们不妨先从归并排序出发一探究竟：

#include <stdio.h>
#include <stdlib.h>

void merge(int a[], int l, int mid, int r)
{
    int n = r - l + 1;
    int *temp = (int *)malloc(n * sizeof(int));

    int i = l;       // 左指针起始索引
    int j = mid + 1; // 右指针起始索引
    int k = 0;       // 数组当前位置索引

    // 比较当前指针值的大小
    while (i <= mid && j <= r)
    {
        if (a[i] <= a[j])
        {
            temp[k] = a[i];
            i++;
        }
        else
        {
            temp[k] = a[j];
            j++;
        }
        k++;
    }

    // 放入左数组剩余元素
    while (i <= mid)
    {
        temp[k++] = a[i++];
    }

    // 右数组的剩余元素
    while (j <= r)
    {
        temp[k++] = a[j++];
    }

    // 覆盖原数组
    for (int i = 0; i < n; i++)
    {
        a[l + i] = temp[i];
    }

    free(temp);
}

void merge_sort(int a[], int l, int r)
{
    if (l == r)
        return; // 终止条件：只有一个元素

    int mid = (l + r) / 2;

    merge_sort(a, l, mid);
    merge_sort(a, mid + 1, r);

    merge(a, l, mid, r); //排序合并子数组
}

int main()
{
    int a[] = {5, 2, 9, 1, 3};
    int n = sizeof(a) / sizeof(a[0]);

    merge_sort(a, 0, n - 1);

    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    return 0;
}

归并排序基于分治思想，即先拆再合。将原问题的待排序列分成多份更小规模的同类子问题，通过递归拆分/合并子问题来达到“先分后治”的目的。而每次递归均是原问题规模的1/2。这里就回答了我们之前的问题： $log_2 n$ 就是这么来的，它的含义就是这颗树要递归的最大深度。而前面的 $n$ 呢？不难理解，每一层的节点之间均需要进行比较合并。而每一层的子问题的规模从整体上看均是一次 $n$ 个元素之间的比较。所以归并排序的时间复杂度就是 $O(n\log_2 n)$ 。

信息是对不确定性的消除

换一个角度，当我们从香农的信息论视角再看这个问题时，也可以得到一个很好的答案。

香农将信息看成是一种消除不确定性的工具。

那么，什么是不确定性？不确定性就是多种可能性同时存在。而我们要找的便是其中的某一条，这就很符合排序算法的描述。

掷一枚骰子，在抛出之前，我们可能会得到1到6中的任何一个，在抛出骰子之前，我们会面对着6种可能，这就是一种不确定性。而当骰子掷出来，结果出现，不确定性消失了。这个过程中消除的可能性就是获得的信息。

那么刚刚这个过程消除了多少的不确定性呢？或者说抛掷一枚骰子的动作会给我们带来多大的信息量呢？香农给出了关于信息量的定量描述：

I = -\log_2(p)

回到排序问题，给定n个不同的数字，那么就有n!种不同的排列组合方式。在进行排序前，我们对这个问题完全处于未知，n!种排列都有可能。而排序算法做的，就是消除不确定性，我们期望排序后，只剩下唯一正确的排列。所以，排序这个问题固有地需要消除的不确定性就是从n!种可能中确定唯一一种，代入信息量公式，就是需要 $\log_2(n!)$ 比特的信息我们才可以得到唯一确定的那一种答案。

$\log_2(n!)$ 说明了什么

从信息论的角度， $\log_2(n!)$ 代表了排序问题本身的信息内容，也就是说如果我们期望从 $n!$ 种组合中得到唯一的那一种确定的答案时，我们至少就需要引入 $\log_2(n!)$ bit的信息。也就是说，如果我们期望给排序算法一个待排序列，在运行一次后得到排序好的那一种结果时，排序算法在这次运行结束后至少要提供 $\log_2(n!)$ bits信息。

而每一次比较能提供给我们多少信息呢？答案是1bit。因为每一次比较均是两个元素的比较，结果无非是a > b or a < b两种，代入香农公式得 $\log_2(2) = 1$ 。显然一次比较仅会消除1bit的不确定性，即我们至少需要 $\log_2(n!)$ 次比较才能唯一确定排好序的那种情况。

这是一个无论用什么算法来排序，都无法绕过的事实：无论快速排序还是归并排序，无论你想到多么聪明的技巧，只要选择用比较来完成排序，就必须获取足够的信息来区分n!种排列——你需要多少信息，问题本身已经决定了，而不是我们没有发现更好的，只不过快速排序、会并排序的设计思想恰好满足了最快的要求，刚好满足。

Stirling公式

$\log_2(n!)$ 似乎和 $n\log_2(n)$ 长得也不太一样，这里使用了斯特林公式近似化简：

斯特林公式[^]（只保留主项）：

n! \approx (n/e)^n \sqrt{2\pi n}

取以 2 为底的对数，有：

\log_2(n!) \approx \log_2\left( (n/e)^n \sqrt{2\pi n} \right)

化简：

\log_2(n!) \approx \log_2\left( (n/e)^n \right) + \log_2\left( \sqrt{2\pi n} \right)

继续展开：

\log_2(n!) \approx n \log_2\left( \frac{n}{e} \right) + \tfrac{1}{2} \log_2(2\pi n)

继续可以写成：

\log_2(n!) = n\log_2 n - n\log_2 e + O(\log n)

于是主导项就是：

\log_2(n!) = \Theta(n\log_2 n)

这也就解释了，基于比较的排序在信息论意义上的下界是 $\Omega(n\log_2 n)$ ，像快速排序、归并排序这样的算法已经在这个数量级上是「最优」的了。

小结

从传统算法分析的角度，我们通过归并排序的递归过程，看到了时间复杂度中 n 和 log_2 n 分别对应的含义：n 来自每一层对所有元素的遍历与比较，log_2 n 则来自递归树的高度。而从信息论的视角，排序问题本身蕴含了 log_2(n!) 这么多比特的信息量——想要在 n! 种排列中确定唯一的一种，就必须至少消除这么多不确定性。

只要是基于比较的排序算法，每一次比较最多只能带来 1 bit 的信息增量，那么无论我们怎样设计比较顺序，都无法逃过需要 O(n\log_2 n) 次比较这一下界。换句话说，像快速排序、归并排序这类平均时间复杂度达到 O(n\log_2 n) 的算法，并不是“暂时还没被超越”，而是在这一范式（基于比较）下已经达到了量级上的最优。

参考资料

[1] https://podcasts.apple.com/cn/podcast/vol-27-%E4%BB%8E%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E8%81%8A%E8%81%8A%E8%BD%AF%E4%BB%B6%E5%92%8C%E4%BF%A1%E6%81%AF%E8%AE%BA/id1769779641?i=1000705043161

[2] https://zh.wikipedia.org/zh-cn/%E5%8F%B2%E7%89%B9%E9%9D%88%E5%85%AC%E5%BC%8F