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.