BFPRT

BFPRT refers to the Blum-Floyd-Pratt-Rivest-Tarjan algorithm, a deterministic selection method for identifying the k-th smallest element in an unsorted list. It is also commonly called the Median of Medians algorithm. The key feature is a guaranteed worst-case linear time performance for selecting order statistics.

The algorithm operates by dividing the input into groups of five elements. It computes the median of each group, then recursively finds the median of those medians to serve as a pivot. The original array is partitioned into elements less than, equal to, and greater than this pivot. Depending on the value of k, the algorithm recurses into the appropriate partition, adjusting k when necessary, until the k-th smallest element is found. The use of a carefully chosen pivot ensures that a substantial fraction of elements are discarded in each step, enabling linear time in the worst case.

In terms of complexity, BFPRT guarantees O(n) time for any input of size n. The space usage is largely driven by recursion; with in-place partitioning, the extra space can be kept to a small constant plus the recursion stack, yielding logarithmic depth in practice. The algorithm is more complex to implement than randomized alternatives (such as Quickselect with random pivots) and tends to have larger constants, so it is less common in everyday use where average-case performance suffices. However, it provides a robust worst-case performance guarantee, making it suitable for systems where predictable timing is essential.

History and naming: the method was introduced by Blum, Floyd, Pratt, Rivest, and Tarjan in the early 1970s, and the approach became a foundational result in deterministic selection and algorithm analysis.