Question

Can Merge Sort Time Complexity be O(n^2) in any condition?

Comments

No, merge sort has an upper bound of $O(n \log n)$

---

I think it will be θ(nlogn),O(nlogn) which is also equal to O(n^2)..it will be never be θ(n^2)

---

Yes time complexity can be $O(n^2)$ if you use merge sort with inplace.

---

The time complexity of Merge sort is (nlogn) for all three cases i.e best, average and worst case.

---

Yes it can be O(n$^{2}$) in case of in-place, when data structure used is array.

Otherwise in case of linked list it will be O(nlogn) only.

---

@aambazinga in case of inplace with linked list it should take $O(n^2)$ time. Right?

---

@Shubhanshu no it's O[nlogn] see this it will be clear. https://www.geeksforgeeks.org/merge-sort-for-linked-list/

---

Thanks.

By default MS on LL is inplace only. But on array it is outplace.

---

What's in place and out place in merge sort?