Splitting a set of points in the plane evenly and sorting it

Question

Input: A set of points P(x,y). There are two versions of it - Px, sorted by x and Py, sorted by y.

Output: The two even halves of Px, sorted by y.

The trick here is that it has to work in linear time, otherwise, it's rather useless. What I've come up with so far is finding the midpoint of Px, let's call it Px[mid] and then iterating over Py, checking if each point's x coordinate is bigger than Px[mid] and then assigning it to the appropriate half.

Example:

Px = [(1,7),(2,3),(3,1),(4,-2)]
Py = [(4,-2),(3,1),(2,3),(1,7)]
Px[midpoint] = (2,3)
Ly = [(2,3),(1,7)]
Ry = [(4,-2),(3,1)]

This works quite well, if you account for points with equal x coordinates and compare said points by y instead (and vice versa), which sorts them in a way that avoids potential surprises. Where it fails is the following case:

Px = [(1,7),(2,-3),(2,-3),(4,-2)]
Py = [(2,-3),(2,-3),(4,-2),(1,7)]
midpoint = 2
P[midpoint] = (2,-3)
Ly = [(2,-3),(2,-3),(1,7)]
Ry = [(4,-2)]

I can't seem to think of a way to exclude non-distinct points from the left half, when they're equal to the midpoint. Again, keep in mind that this has to work in linear time, so I can't just split Px into two halves and search for points which might belong to it for the odd case.