introsort 比归并排序（时间复杂度）好吗？

Question

请解释为什么C++ sort() 算法使用introsort？在哪些情况下它比常规的 mergeSort 算法表现更好

Answer 1

is introsort better than merge sort (Time Complexity)?

两种算法具有相同的渐近时间复杂度：在最坏情况和平均情况下均为 O(N log N)。

Please explain why does C++ sort() algorithm uses introsort?

假设您指的是标准算法 std::sort，则不能保证使用 introsort 来实现。您可能指的是一些特定的实现。

and in which cases does it perform better than regular mergeSort algorithm

通常在数据具有高缓存局部性且输入范围长度较小的情况下。

Answer 2

在大多数情况下，快速排序优于归并排序。但快速排序对几乎已排序的数据表现不佳； introsort 修复了一些反常情况。