Algorithms and Data Structures · Senior · Question 32 of 75
What is introsort and why is it used in C++ std::sort?
- ✓Correct answer: Quicksort that falls back to heapsort when recursion gets too deep
- 2A sort that picks the algorithm by inspecting the data type
- 3Merge sort that uses insertion sort on every level
Explanation
Quicksort is fast on average, but its O(n²) worst case can be triggered. Introsort limits recursion depth to about 2 log n and switches to heapsort, guaranteeing O(n log n) while keeping quicksort speed.