# Mergesort with $O(n^2 \log n)$ runtime

I have a task where i need to find a problem in which mergesort has to have a runtime of $O(n^2 \log n)$. In our lecture we said that the runtime is $O(n \log n)$ assuming that every comparison is $O(1)$. I think that I have to work with comparison-complexity but I dont know how to create a runtime of $O(n^2 \log n)$ since mergesort has best and worst-case complexity of $O(n \log n)$. Could anybody help me out creating a problem to achieve a runtime of $O(n^2 \log n)$ ?

• Hint: try to think of your input as not being necessarily a set of atomic objects. – André Souza Lemos May 16 '15 at 16:10
• @AndréSouzaLemos so you mean if i take for instance vectors except of numbers than it will work ? – thedude May 16 '15 at 16:33
• That would be a start. – André Souza Lemos May 16 '15 at 16:39
• @AndréSouzaLemos thank you i did not think of this option ! i think that will help me a lot :-) – thedude May 16 '15 at 16:41

Remember what $O(\cdot)$ means. You don't need to do anything. Mergesort has a running time of $O(n\log n)$ which is already $O(n^2 \log n)$, $O(2^n)$ and $O(\text{any larger function you want})$.