The Hundred Slowest Requests

You have 5,000,000 request records in memory and need the 100 with the highest latency, printed in descending latency order. Sorting the whole array works but is the baseline you are trying to beat.

More than one option is correct. Which approaches are both correct and asymptotically cheaper than sorting all 5,000,000 records?

Scan once keeping a min-heap of size 100, popping the smallest whenever the heap exceeds 100, then drain it and reverse the 100 results

std::partition the array around the mean latency, then sort the upper part

std::partial_sort(v.begin(), v.begin() + 100, v.end(), byLatencyDesc), which costs about $n \log k$ comparisons

std::nth_element(v.begin(), v.begin() + 100, v.end(), byLatencyDesc), then std::sort on just that prefix: linear on average plus $k \log k$

Scan once keeping a max-heap of size 100, popping the top whenever the heap exceeds 100, then drain it