Bah, I'll be happy if I could even get correct averages. I see pipelines getting value X1 from a server that served 100 requests, another value X2 from a server that served one request, and then it returns (X1+X2)/2.

The mean is something you can easily compute progressively and with trivial resources. Median and percentiles, on the other hand, can be super expensive and potentially unsuitable for some real-time applications, since you need to maintain a sorted list of all relevant samples.

Not surprising, because computing mean is O(n) and median is O(n log n).

Lack of resources or pure laziness doesn't make it the right measure to use though.

Introselect is O(n), right?