There is actually a paper about exactly this: "Optimal Pivot Selection in Fast Weighted Median Search" ieeexplore.ieee.org/iel5/78/6236322/06193457.pdf It gi

There is actually a paper about exactly this: "Optimal Pivot Selection in Fast Weighted Median Search" ieeexplore.ieee.org/iel5/78/6236322/06193457.pdf It gives a formula for the optimal subset size to use to find the pivot and also does some optimization after the first partitioning step.