How to find i largest numbers in unsorted array in O(n) where i <= n^(1/2) If we have length $n$ unsorted array such that each element is integer and different, how to find $i$ largest numbers in linear time O(n)? but $i \leq n^{\frac{1}{2}}$.
For example, if we have $A = [11, 6, 8, 1, 9, 100, 88]$ and input $i = 2$, then output is $[100, 88]$ (sorted).
Use a selection algorithm to find the $i$th largest number.  This can be done in linear time.  Then, do a second scan over the array to find all numbers larger than the $i$th largest number.  (With many selection algorithms, this last step is unnecessary, as they partition the array into elements smaller than the $i$th largest and larger than the $i$th largest.)