In computer science, introselect (short for "introspective selection") is a selection algorithm that is a hybrid of quickselect and median of medians which has fast average performance and optimal worst-case performance.
[1] However, in most C++ Standard Library implementations, a different "introselect" algorithm is used, which combines quickselect and heapselect, and has a worst-case running time of O(n log n).
[2] The C++ draft standard, as of 2022, does not have requirements on the worst-case performance, therefore allowing such choice.
Introselect works by optimistically starting out with quickselect and only switching to a worst-case linear-time selection algorithm (the Blum-Floyd-Pratt-Rivest-Tarjan median of medians algorithm) if it recurses too many times without making sufficient progress.
Simply limiting the recursion to constant depth is not good enough, since this would make the algorithm switch on all sufficiently large lists.