Algorithms for Selecting the Median and the kth Element

• Median
  • Majority element
  • Merging sorted sequences
• kth element

---

Prelude: The Majority Element

Using a strict definition, a majority element appears more than $n/2$ times.

Under this definition, the majority element is also the median.

How can we find it? A classic algorithm is the Boyer–Moore majority vote.

If a majority element exists and we remove a pair of different values from the array, there are two cases:

• The majority element is not in the pair, so the majority remains unchanged after removal.
• The majority element is in the pair. Since $n_{maj}>n-n_{maj}$ implies $n_{maj}-1>(n-n_{maj})-1$, it remains the majority.

This is a classic decrease-and-conquer algorithm.

Following this idea, every element can “vote” during a single pass to produce a final candidate.

ALGORITHM FindMajority(A):
    // Input: an array A of length n
    // Output: A's majority element, or null if none exists

    // Phase 1: find a candidate
    candidate ← null
    count ← 0

    FOR EACH element IN A DO:
        IF count == 0 THEN:
            candidate ← element
            count ← 1
        ELSE IF element == candidate THEN:
            count ← count + 1
        ELSE:
            count ← count - 1
    END FOR

    // Phase 2: verify the candidate (optional when a majority is guaranteed)
    actual_count ← 0
    FOR EACH element IN A DO:
        IF element == candidate THEN:
            actual_count ← actual_count + 1
    END FOR

    IF actual_count > length(A) / 2 THEN:
        RETURN candidate
    ELSE:
        RETURN null

---

Combining Two Sorted Sequences

decrease and conquer

Using decrease and conquer, how can we find the median of two sorted sequences after combining them?

First find their individual medians, $m_A$ and $m_B$.

• If they are equal, we have found the combined median.
• Otherwise, their ordering tells us that the answer lies in either the right half of $A$ plus the left half of $B$, or the left half of $A$ plus the right half of $B$. Recurse on those reduced ranges.

This gives the recurrence:

$$T(n) = T(n/2)$$

and therefore $O(\log N)$ time.

leetcode

I had previously solved this problem on LeetCode, where the requested approach traversed only the shorter array to find the median.

The key insight is that once the partition position $i$ in $A$ is fixed, the corresponding position $j$ in $B$ is determined, because the total number of elements on the left side is fixed.

We only need to test whether each pair of partition positions is valid: $A[i-1]\le B[j]$ and $B[j-1]\le A[i]$. The answer is then obtained from these four boundary values.

Binary-Search Partitioning

The two ideas can be combined. Instead of repeatedly discarding fixed halves, use binary search on the shorter sequence to find a position $i$ whose corresponding $j$ satisfies the partition conditions.

This takes only $O(\log(\min(m,n)))$ time and appears to require fewer edge cases than the first approach, where selecting left and right ranges can produce unequal lengths.

---

1. Quickselect

Core idea: decrease and conquer.

Quickselect finds the $k$th-smallest element in an unsorted array. It uses Quicksort’s partition operation, but unlike Quicksort’s recursion into both sides, it enters only the side containing the target. The recursion therefore does not expand into a binary tree and has linear expected complexity.

Procedure

1. Pivot selection: choose a random element or an endpoint as the pivot.
2. Partitioning: divide the array into three logical regions:
   • Q (Smaller): values below the pivot
   • L (Equal): values equal to the pivot
   • G (Greater): values above the pivot
3. Branching: use the relationship between $k$ and the partition boundaries to return the pivot or recurse into Q or G.

Time Complexity

• Average case: assume every partition divides the array evenly.

  $T(n) = T(n/2) + O(n)$

  Expanding the geometric series gives $T(n)=n+n/2+n/4+...+1\approx2n$, so the average complexity is $O(n)$.

• Worst case: the pivot is always an extreme value, eliminating only one element per step.

  $T(n) = T(n-1) + O(n)$

  Summing the arithmetic series $n+(n-1)+...+1$ gives a worst-case complexity of $O(n^2)$.

---

2. BFPRT (Median of Medians)

Core idea: deterministic pivot selection.

BFPRT prevents ordinary Quickselect from degenerating in the worst case. A preprocessing procedure theoretically guarantees sufficiently balanced partitions.

In essence, it avoids choosing an extreme pivot in Quickselect by first computing a median-like representative.

Procedure

1. Grouping: divide the $n$ elements into groups of five.
2. Local medians: sort each group and take its median.
3. Recursive pivot selection: recursively apply BFPRT to these $n/5$ medians and call their median $x$.
4. Partitioning: use $x$ as the pivot for a three-way partition.

Time Complexity

BFPRT’s complexity has three parts:

1. $O(n)$: linear work for grouping and finding local medians.
2. $T(n/5)$: the cost of recursively finding the median of medians.
3. $T(7n/10)$: the largest remaining subproblem in the worst case.

Why $7n/10$?

Half of the group medians are smaller than $x$. In each of those groups, three elements—including the median itself—are less than or equal to that group median.

Therefore, at least $\frac{n}{5}\times\frac{1}{2}\times3=\frac{3}{10}n$ elements are guaranteed not to exceed $x$. Symmetrically, at least $3n/10$ elements are not smaller than $x$. At worst, only the remaining $7n/10$ elements need further processing.

Final recurrence:

$T(n) \leq T(n/5) + T(7n/10) + O(n)$

Since $1/5+7/10=9/10<1$, the recursion tree converges, proving that $T(n)=\mathbf{O(n)}$.

---

3. Comparison and Tradeoffs

In practice, Quickselect is more common than BFPRT. Although BFPRT guarantees linear worst-case time, its extra computation usually hurts performance on ordinary randomized inputs.

Property	Quickselect	BFPRT
Theoretical worst case	$O(n^2)$	$O(n)$
Practical constant factor	Very small (about $2n$)	Large (about $10n$–$20n$)
Memory-access pattern	Cache-friendly sequential access	More cache misses due to complex access patterns
Implementation difficulty	Simple	Complex
Typical use	std::nth_element with Introselect	Algorithm theory and security-sensitive tasks

Why Is Quickselect More Common?

1. Memory locality: Quickselect’s linear scan makes excellent use of CPU L1/L2 caches. BFPRT’s grouping and repeated extraction disrupt spatial locality.
2. Branch prediction: Quickselect has straightforward control flow that modern CPUs predict well. BFPRT’s nested recursion and grouping logic can stall the pipeline.
3. Probabilistic guarantees: with randomized pivot selection, the chance of encountering $O(n^2)$ behavior in practice is extraordinarily small—smaller than the probability of a hardware failure.