Computational complexity of calculating mean vs median? Suppose we have a list $L$ consisting of $N$ numbers (may include repetitions).

I am curious which is more computationally intensive to calculate, the mean or the median?

Naively, I would suppose calculating the mean involves summing up the $N$ numbers and then dividing by $N$, hence it has linear $O(N)$ complexity.

Computing the median would need to perform some sort of sorting algorithm, https://en.wikipedia.org/wiki/Sorting_algorithm, it seems the best algorithm performs at $O(n\log n)$ complexity.

Hence, for general $N$, it is more computationally intensive to calculate median? Is my reasoning correct?

Thanks for any help.
You can find the median in linear time using the linear time selection algorithm. There are also faster randomized algorithms such as quickselect and Floyd–Rivest.

The two tasks are really incomparable, since computing the mean requires arithmetic (mainly addition) whereas computing the median requires comparisons.