c++ - introsort 比合并排序（时间复杂度）更好吗？

Question

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

Answer 1

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

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

请解释为什么 C++ sort() 算法使用 introsort？

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

以及在哪些情况下它比常规的 mergeSort 算法表现更好

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

Answer 2

在大多数情况下，快速排序优于合并排序。但是快速排序在开始时几乎已排序的数据上表现不佳；introsort 修复了一些不正常的情况。