nthSmallest<T> function

T? nthSmallest<T>(
  1. Iterable<T> items,
  2. int k,
  3. Comparator<T> compare
)

Returns the element that would sit at 0-based index k if items were sorted by compare, without paying for a full sort.

Quickselect averages O(n) versus O(n log n) for sort-then-index, which matters when you need a single order statistic (median, 90th percentile, 2nd smallest) from a large collection. Partitions a private copy, so items is never mutated.

Returns null when k is out of range (k < 0 or k >= length) rather than throwing, so the empty / bad-index case is handled at the call site.

Example:

nthSmallest<int>([7, 2, 5, 1], 1, (a, b) => a.compareTo(b)); // 2 (2nd smallest)

Audited: 2026-06-12 11:26 EDT

Implementation

T? nthSmallest<T>(Iterable<T> items, int k, Comparator<T> compare) {
  final List<T> a = items.toList();
  if (k < 0 || k >= a.length) {
    return null;
  }

  int lo = 0;
  int hi = a.length - 1;
  while (lo < hi) {
    final int pivotIndex = _partition(a, lo, hi, compare);
    if (pivotIndex == k) {
      break;
    }
    // Recurse into only the side that contains rank k — this is what makes
    // quickselect linear on average rather than sorting both halves.
    if (pivotIndex < k) {
      lo = pivotIndex + 1;
    } else {
      hi = pivotIndex - 1;
    }
  }
  return a[k];
}