Efficient multiselection algorithm

Efficient multiselection algorithm

I have to implement an algorithm that solves the multi-selection problem.
The multiselection problem is:
Given a set S of n elements drawn from a linearly ordered set, and a set K
= {k1, k2,...,kr} of positive integers between 1 and n, the multiselection
problem is to select the ki-th smallest element for all values of i, 1 <=
i <= r
I need to solve the average case on È(n log p) I've found a paper that
implements the solution I need, but it assumes that there are no repeated
numbers on the set S. The problem is that I can't assume that and I don't
know how to adapt the algorithm of that paper to support repeated numbers.
The paper is here:
http://www.ccse.kfupm.edu.sa/~suwaiyel/publications/multiselection_parCom.pdf
and the algorithm is on the second page. Any tips are welcome!