c++algorithmsortingmergesortintrosort

is introsort better than merge sort (Time Complexity)?

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

Solution

  • 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.