An Ω(n log n) lower bound for computing the sum of even-ranked elements

Marc Mörig, Dieter Rautenbach, Michiel Smid +1

Given a sequence A of 2n real numbers, the Even-Rank-Sum problem asks for the sum of the n values that are at the even positions in the sorted order of the elements in A. We prove…