I am working on an algorithm to calculate the median of the current input stream of numbers. I am using the following method (I know it is not the best but I need to calculate its complexity).
- Sort the numbers received until now
- Return the middle element.
Sorting takes $n\log n$ time so the complexity for this approach is $$1\log1 +2\log2 +3\log3 +\ldots +n\log n,$$ where $n$ is the number of input elements.
How do I calculate the sum of such a series?