Inbuilt sort function

#1

What exactly is introsort used behind inbuilt sort function in c++?

#2

Hey @sarthakj2099
In the inbuilt sort function of C++
-Quick Sort is the core algorithm
-Quicksort’s worst performance may be O(n^2). To avoid the worst case the recursion depth is recorded. If the recursion depth increase 2x log(n) then it falls back to Heap Sort. This ensures optimal performance. This combination of Quick and Heap sort is called Intro Sort.
-Pivot selection strategies are also optimised. One of the most common optimisations is taking median of 3 random pivots
-When the size of array decreases in the recursion tree, Insertion Sort is used. This is because insertion sort tends to be faster when number of elements are less and the array is almost sorted.

1 Like
#3

@sarthakj2099
Please mark the doubt as resolved if you’ve got it.

#4

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.