为何LeetCode上O(NlogN)算法比O(N)算法运行表现更优？

我在解决LeetCode「字符频率排序」问题时发现一个有趣的现象：理论复杂度更高的O(NlogN)算法，实际运行速度反而比理论O(N)的桶排序算法更快。

解法1：基于Counter的most_common实现 #

def frequencySort(self, s: str) -> str:
    return ''.join(char * occurences for char, occurences in Counter(s).most_common())

LeetCode分析的复杂度：

运行时间：

解法2：桶排序实现 #

def frequencySort(self, s: str) -> str:
    count = Counter(s)
    buckets = defaultdict(list)

    for char, cnt in count.items(): 
        buckets[cnt].append(char)
    res = []

    for i in range(len(s), 0, -1): 
        for c in buckets[i]:
            res.append(c * i)

    return "".join(res)

LeetCode分析的复杂度：

运行时间：

这种反直觉的结果主要是因为Python内置的Counter.most_common()方法底层经过了极度优化，而手动实现的桶排序在常数因子上开销更大，最终导致实际运行效率不如前者。

内容的提问来源于stack exchange，提问作者bulut