Splitting a set of points in the plane evenly and sorting it
This is not so hard to fix. First, calculate the median $m$. Then calculate the number of points strictly left of the median $\ell$. Take all of them from Py, and take the first $n/2-\ell$ points whose $x$ value is $m$ (where $n$ is the total number of points). These form the first half, and the rest of the points form the second half.