Computing order statistics $1,2,4,8,\ldots,n$
You can find all of these order statistics in $O(n)$. First, find the maximum (order statistic $2^k$) in time $O(n)$. Then, find the median (order statistic $2^{k-1}$) in time $O(n)$, and remove all larger elements. Find order statistic $2^{k-2}$ in time $O(n/2)$, and remove all larger elements. And so on. The total running time is $$O(n + n/2 + n/4 + \cdots) = O(n).$$