Multi Selection

Multi Selection finds several order statistics at once. Instead of running selection repeatedly for each rank, it reuses partition results to reduce total work.

This is useful when you need multiple quantiles, percentiles, or split points.

Problem

Given an array $A$ of length $n$ and a sorted list of ranks:

k_1 < k_2 < \dots < k_m

find all corresponding elements.

Algorithm

Use a recursive partitioning strategy similar to Quickselect. At each step, choose a pivot and partition the array. Then distribute the target ranks across the left and right partitions.

multi_select(A, ranks):
    if ranks is empty:
        return

    choose pivot
    partition A into L, E, R

    let l = size(L)
    let e = size(E)

    split ranks into:
        ranks_L = [k for k < l]
        ranks_E = [k for l <= k < l + e]
        ranks_R = [k for k >= l + e]

    for k in ranks_E:
        answer[k] = pivot

    multi_select(L, ranks_L)
    multi_select(R, [k - l - e for k in ranks_R])

Key Idea

Each partition step resolves all ranks that fall within the pivot group. The remaining ranks are passed to smaller subproblems. This avoids reprocessing the entire array for each rank.

Example

Let:

A = [7, 2, 9, 4, 3]

and ranks:

[1, 3]

Sorted order:

[2, 3, 4, 7, 9]

Results:

rank 1 → $3$
rank 3 → $7$

Multi Selection finds both values in a shared partition process.

Correctness

Partition preserves relative ordering with respect to the pivot. Each recursive call adjusts ranks so they refer to the correct subarray. Every rank eventually falls into a pivot group or a base case.

Thus each requested rank is resolved correctly.

Complexity

case	time
average	$O(n \log m)$
best structured splits	$O(n)$
worst	$O(n^2)$

With good pivot selection or randomization, the expected time is close to linear for small $m$ .

Space:

O(m + \log n)

When to Use

Use Multi Selection when:

multiple order statistics are needed
repeated Quickselect would be inefficient
quantiles or percentiles are required

For a single rank, standard Quickselect is simpler.

Implementation

import random

def multi_select(a, ranks):
    result = {}

    def select(arr, ks, offset):
        if not ks:
            return

        if len(arr) == 1:
            for k in ks:
                result[offset + k] = arr[0]
            return

        pivot = random.choice(arr)

        L = [x for x in arr if x < pivot]
        E = [x for x in arr if x == pivot]
        R = [x for x in arr if x > pivot]

        l, e = len(L), len(E)

        ks_L = [k for k in ks if k < l]
        ks_E = [k for k in ks if l <= k < l + e]
        ks_R = [k for k in ks if k >= l + e]

        for k in ks_E:
            result[offset + k] = pivot

        select(L, ks_L, offset)
        select(R, [k - l - e for k in ks_R], offset + l + e)

    select(a, ranks, 0)
    return result

func MultiSelect(a []int, ranks []int) map[int]int {
	result := make(map[int]int)

	var selectFn func([]int, []int, int)

	selectFn = func(arr []int, ks []int, offset int) {
		if len(ks) == 0 {
			return
		}

		if len(arr) == 1 {
			for _, k := range ks {
				result[offset+k] = arr[0]
			}
			return
		}

		pivot := arr[len(arr)/2]

		var L, E, R []int
		for _, x := range arr {
			if x < pivot {
				L = append(L, x)
			} else if x > pivot {
				R = append(R, x)
			} else {
				E = append(E, x)
			}
		}

		l, e := len(L), len(E)

		var ksL, ksE, ksR []int
		for _, k := range ks {
			if k < l {
				ksL = append(ksL, k)
			} else if k < l+e {
				ksE = append(ksE, k)
			} else {
				ksR = append(ksR, k)
			}
		}

		for _, k := range ksE {
			result[offset+k] = pivot
		}

		selectFn(L, ksL, offset)
		shifted := make([]int, len(ksR))
		for i, k := range ksR {
			shifted[i] = k - l - e
		}
		selectFn(R, shifted, offset+l+e)
	}

	selectFn(a, ranks, 0)
	return result
}