Point rank in 2D plane time complexity? I'm reading about the algorithm of finding the ranks of all points in a 2D plane, I don't understand the time complexity formula for it. It has four steps:


Compute the median of x-coordinates of all point, and divide the plane into two half Left, and Right.
Recursively do 1. then when there is only 1 point, rank(that point)=0.
Sort points by y-coordinate in Left, and Right separately.
Update Right.


I understand the idea of these steps, and 3. has complexity $O(n\log n)$, but the time complexity formula in my book is

$$T(n)=2T(n/2)+\Theta(n),$$

why the last term is not $\Theta(n\lg n)$? That is my current idea is that the $T(n)=\Theta(n\lg^2n)$, by applying master's theorem.
I think I may solve it but I'm not sure: In short the sorting can be done in $\Theta(n)$, so the book statement, hence my assumption, is not correct. The "Sort points by y-coordinate in Left, and Right" actually only need to merge it, and this step is $\Theta(n)$.