is introsort better than merge sort (Time Complexity)?

Question

Please explain why does C++ sort() algorithm uses introsort? and in which cases does it perform better than regular mergeSort algorithm

Answer 1

is introsort better than merge sort (Time Complexity)?

Both algorithms have the same asymptotical time complexity: O(N log N) in both worst and average case.

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

Assuming you mean the standard algorithm std::sort, it is not guaranteed to be implemented using introsort. You may be referring to some specific implementation(s).

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

Usually in cases where the data has high cache locality and the length of the input range is small.

Answer 2

In most cases, quicksort is preferable to merge sort. But quicksort behaves badly on data that’s nearly sorted to begin with; introsort fixes some of the perverse cases.