Intertube上处理基于比较的排序的任何页面都将告诉您，排序
不能 比O(n lg n)使用比较排序快。也就是说，如果您的排序算法通过将2个元素彼此进行比较来确定顺序，那么您做得更好。示例包括快速排序，气泡排序，合并排序。

一些算法（例如计数排序或存储桶排序或基数排序）不使用比较。相反，它们依赖于数据本身的属性，例如数据中值的范围或数据值的大小。

这些算法 可能 具有更快的复杂度。这是一个示例方案：

您正在对10^6整数进行排序，并且每个整数都在0和之间10。然后，您可以只计算零，一，二等的数量，然后按排序顺序将其吐出。这就是countsort的工作原理，O(n + m)即m您的基准可以采用的值数量（在这种情况下为m=11）在哪里。

另一个：

您正在对10^6所有最多为5字符的二进制字符串进行排序。您可以为此使用基数排序：首先根据它们的第一个字符将它们分成2个存储桶，然后对第二个字符（第三，第四和第五个）进行基数排序。只要每个步骤都是稳定的排序，您就应该在中得到一个排序完美的列表O(nm)，其中m是数据中位数或位数（在这种情况下为m=5）。

但是在一般情况下，排序速度不能比O(n lg n)可靠排序（使用比较排序）快。