Merge sort splits the array into two halves, recursively sorts both and merges their sorted outputs. During the merge algorithm, compare the first unconsumed entry of each half, emit the smaller and advance that half; append the remainder when one half ends. The emitted prefix is always sorted and contains exactly the already consumed entries, proving the merge step correct. Induction on input length proves the full sorting algorithm correct.
The recurrence relation is for powers of two, with constant base cost. In the Master theorem, and , matching the merge term. Hence . Floor/ceiling splits give the same bound for arbitrary ; conventional merging uses auxiliary space.
On a worst-case branch, the described sequential quarter-point tests make three equality tests per reduction, giving until constant size. Thus . Ordinary binary search makes one equality test per halving: , so .
Both searches take time, but the specified quaternary search uses asymptotically as many equality tests. A quarter-sized branch does not compensate for the three sequential pivots. The numerical ratio concerns precisely the unit equality-test model in the paper; counting ordering comparisons, array accesses or a differently arranged pivot decision tree requires its own constants.
Sort records
(value,original_index) by value using merge sort. For each record with value , run binary search for value among the sorted records; return the two retained original indices at the first match, otherwise return nil after all records.If a valid pair exists, its smaller entry is inspected and the matching doubled entry is found by binary search. Conversely every returned pair satisfies the requested equality. Positivity gives , so the returned entries are distinct even if other entries repeat. Sorting costs , and at most binary searches cost altogether. Total time is , using the paper's unit-cost arithmetic model; doubling large machine integers would require overflow-safe arithmetic.
Keep each weight attached to its value while sorting, then return the first cumulative weight reaching one half:
weightedMedian(A, weights):
R = records (A[i], weights[i], i), sorted by first component
cumulative = 0
for (value, weight, original_index) in R:
cumulative = cumulative + weight
if cumulative >= 1/2:
return original_indexAll weights are positive, so the cumulative weights strictly increase. At the returned entry the mass strictly to its left is below one half, while the mass strictly to its right is at most one half. This is the lower weighted median, including the exact equality case: stop at the earlier value whose cumulative mass is exactly one half. Sorting takes and the scan takes , giving time.
Maintain a residual cumulative-weight target , initially , 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 , with the desired answer the first cumulative weight reaching 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 entries. Therefore . 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.
Articles by others on the same topic
There are currently no matching articles.