To see this complexity result, let P(N) be the work to process N items starting with a popularity splits and let L(N) be the work to process N items starting with a lexicographic splits.
where α = 2−p, when p is the probability that the popular half contains sufficient matches.