Choose the median in constant time, because the algorithm is implemented as an array and you can find the median in constant time.
Then, split the array with respect to the median.
The recurrence relation will be:
T(n) = 2T($\frac{n}{2}$) + 1
(1 because we are doing a constant work and then splitting the array)
Solve by master's theorem, you will get $\Theta (n)$
NOTE: If the data structure used was a linked list or if the elements were not in ascending order, the complexity would have been $\Theta (nlogn)$
