Introselect

Introselect, short for introspective selection, is a selection algorithm that hybridizes quickselect and median of medians, giving fast average performance together with optimal worst case performance. It is related to the introsort sorting algorithm in that both begin with a quick algorithm offering good average performance and low overhead, then fall back to a slower but worst case optimal algorithm if the quick algorithm is not progressing rapidly enough. Both were introduced by David Musser in 1997 to provide generic algorithms for the C++ Standard Library with both fast average and optimal worst case performance, though most Standard Library implementations in practice use a different introselect combining quickselect and heapselect.