Order statistics

The minimum or maximum is found with n - 1 comparisons, and no algorithm can do better: every other element must lose at least one comparison, and each comparison can eliminate only one candidate.

To find both together, compare elements in pairs first. The larger of each pair is a candidate for the maximum and the smaller for the minimum. Each pair costs 1 comparison, then 1 against the running maximum and 1 against the running minimum: 3 comparisons per 2 elements, ⌈3n/2⌉ - 2 in total, instead of 2n - 2.

1static int[] minMax(int[] a) {
2    int min, max, i;
3    if (a.length % 2 == 0) {                         // start with the first pair
4        if (a[0] < a[1]) { min = a[0]; max = a[1]; } else { min = a[1]; max = a[0]; }
5        i = 2;
6    } else { min = max = a[0]; i = 1; }
7    for (; i + 1 < a.length; i += 2) {
8        int small, large;
9        if (a[i] < a[i + 1]) { small = a[i]; large = a[i + 1]; }   // 1 comparison for the pair
10        else                 { small = a[i + 1]; large = a[i]; }
11        if (small < min) min = small;                // 1 comparison
12        if (large > max) max = large;                // 1 comparison
13    }
14    return new int[] { min, max };
15}

The median is the middle value in sorted order. For odd n it is the element at sorted index (n - 1) / 2 (0-based). For even n there are two middle elements: the lower median at n/2 - 1, the upper median at n/2, and many definitions take their average.

Sorting finds it in O(n log n). Quickselect finds it in expected O(n), and the median-of-medians algorithm in worst-case O(n). Two heaps maintain it as values arrive (lesson 19.04).

The k-th smallest (1-based) is at sorted index k - 1. The k-th largest is the (n - k + 1)-th smallest, at sorted index n - k. Always state whether k is 1-based and whether duplicates count separately: in [5, 5, 3] the second largest is 5 if duplicates count and 3 if only distinct values count.

There are three standard solutions, compared below. Sorting is simplest. A heap of size k is best when k is small or when data streams in. Quickselect is fastest on average when the whole array is in memory.

The p-th percentile is the value below which p percent of the data falls. With the nearest-rank method it is the element at rank ⌈p / 100 · n⌉ (1-based): for n = 20 values, the 90th percentile is the 18th smallest.

Other definitions interpolate between neighbouring values, which is what spreadsheets and libraries such as NumPy do by default. State which method you use, because results differ on small samples. Performance monitoring often reports p50, p95 and p99 latency; computing them needs one selection per percentile, not a full sort per query.

1static int percentile(int[] sortedAscending, double p) {   // nearest-rank method, 0 < p <= 100
2    int rank = (int) Math.ceil(p / 100.0 * sortedAscending.length);   // 1-based
3    return sortedAscending[Math.max(rank, 1) - 1];
4}
5
6// 20 latencies, p95 -> rank = ceil(0.95 * 20) = 19 -> the 19th smallest

Rank and select are inverse operations. rank(x) is the number of elements smaller than x (or the 1-based position x would have in sorted order). select(i) returns the element of rank i.

On a static array, rank is a binary search on sorted data (lower bound) and select is an array lookup. When elements are inserted and deleted, you need a structure that supports both quickly: an order-statistic tree, where each node stores its subtree size, or a Fenwick tree over compressed values, both giving O(log n) for rank, select, insert and delete.

1// static data: rank is lowerBound, select is an index
2int rank(int[] sorted, int x) { return lowerBound(sorted, x); }   // elements < x
3int select(int[] sorted, int i) { return sorted[i]; }                 // 0-based