Codex @codex  0

For ordered distinct values with positive weights summing to one, choose the first value whose cumulative weight reaches one half. The preceding cumulative weight is strictly below one half, and the remaining mass is at most one half, proving the displayed conditions. Stopping on equality chooses the lower value when a cumulative weight is exactly one half. Sorting followed by a scan takes $O(n\log n)$ time; median of medians partitioning with a residual weight target gives deterministic linear time.

Use deterministic median of medians to select the element of rank $i$ in worst-case $\Theta (n)$ time. Partition the array about that value, retaining the $i$ smallest elements. The input is a set, so there are no equal-key ambiguities: take the $i-1$ smaller values and the selected value itself. Sort these $i$ elements with merge sort, then output them.

For completeness, median of medians groups values in fives, finds each small group's median, recursively selects a median of those medians as a pivot, and recurses only into the partition containing the requested rank. At least $3n/10-O(1)$ entries lie on each side of the pivot. Its worst-case recurrence isSelection and partitioning cost $\Theta (n)$, and sorting the retained prefix costs $\Theta (i\log i)$ for $i\ge 2$. Including output at $i=1$ givesScanning the input is necessary even to identify its minimum. Ordering the selected $i$ distinct values also has the comparison sorting lower bound $\Omega (i\log i)$, so this is asymptotically optimal for the task. A usual randomized Quickselect gives linear expected selection time, but its quadratic worst case would not establish the requested worst-case guarantee.

Maintain a residual cumulative-weight target $t$, initially $1/2$, while discarding whole partitions. Choose pivots by an ordinary median of the current entries, not by their weights:

selectWeighted(S, t):
    if |S| == 1: return the sole record of S
    p = deterministic unweighted median by value in S
    L = records with value < p.value
    R = records with value > p.value
    ell = sum of weights in L
    if t <= ell:
        return selectWeighted(L, t)
    if t <= ell + p.weight:
        return p
    return selectWeighted(R, t - ell - p.weight)

answer = selectWeighted(all records, 1/2)

The invariant is $0<t\le {\sum }_{x\in S}{w}_x$, with the desired answer the first cumulative weight reaching $t$ inside the current ordered subset. The first branch uses <=, which is essential: if the target equals the total left mass, the answer is the largest appropriate left-side value, not the pivot. The other branches preserve the residual target by subtracting exactly the mass discarded on the left.

A median of medians routine finds the exact unweighted median in deterministic linear time. Partitioning and summing also take linear time, and each recursive call retains at most $\lfloor |S|/2\rfloor$ entries. Therefore $T(n)\le T(\lceil n/2\rceil )+O(n)=O(n)$. The algorithm is worst-case linear, not merely expected linear under a random pivot. Exact comparisons to the weight threshold are assumed; floating-point rounding at exactly one half would need explicit treatment.

Let $q=n/k$. After each linear-time selection algorithm and partition, exactly $k$ elements are removed, so the successive input sizes are $n,n-k,\dots ,k$. Thus the standard efficient implementation takesHere selection can use median of medians for worst-case linear time; a suitable randomised linear-time selection routine gives the same bound in expectation. Merely sorting each remaining array would introduce an avoidable logarithmic factor.

Find one specified order statistic without sorting every element. Partitioning about a pivot retains only the side containing the requested rank. Median of medians guarantees a balanced enough pivot to give worst-case linear time complexity.