The well-known algorithm for computing the $k$-th largest element in an unsorted array of size $n$ runs in $O(n)$ time. How about for a range $[k, k+c]$, where $c$ is not necessarily independent of $n, k$? The obvious brute-force algorithm is to find the $k$th largest using the original $O(n)$-time algorithm, then the $k+1$-th largest the same way, ..., find the $k+c$-th largest (and also, the algorithm outputs these in sorted order). However, this takes $O(nc)$ time, and $c$ can possibly be $\Theta(n)$, which can lead to an $O(n^2)$ algorithm. In this case, we could have just sorted the array and extracted the elements, which takes $O(n \log n)$ time.Is there a better (known) way of doing this? I can't find any references online. 
$k$th Largest Algorithm in a range $[k, k+c]$
algorithms;selection problem
Step 1. Use QuickSelect to find the $k$th largest number in the array.  Call it $x$.Step 2. Use QuickSelect to find the $k+c$th largest number in the array.  Call it $y$.Step 3. Find all elements in the array that are at least $x$ and at most $y$.  This can be done by simply iterating over the array and comparing each element to $x$ and $y$.Each step can be done in $O(n)$ time.  Therefore, the total running time is $O(n)+O(n)+O(n) = O(n)$ time.