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

Question

请解释为什么C ++ sort（）算法使用introsort？在哪种情况下，它的性能比常规的mergeSort算法好？

Answer 1

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

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

请解释为什么C ++ sort（）算法使用introsort？

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

在哪种情况下，它的性能比常规的mergeSort算法好？

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