The current algorithm always calls qsort() which requires $$\Omega(n\log n)$$ even when the first point dominates the rest. It should be possible to implement a natural merge sort that removes dominated points as it sorts and that has $$\Omega(n)$$ . See tommyod/paretoset#50 for more details.