Computer make it possible to find information in large databases. However, the results are often too large to be returned in their entirety to the user who requests them. Computer therefore sort the results by relevance according to their own metrics. They only display the first k results on a page. The user can then go to the next page to view the next $k$ results or even go directly to the $p$-th page to view the k results for that page.
I would like such algorithm in $\Theta(n + k \log k)$