1 votes 1 votes Algorithms algorithms time-complexity sorting + – aditykansara asked Jan 31, 2019 aditykansara 1.4k views answer comment Share Follow See all 9 Comments See all 9 9 Comments reply Gokulnath commented Jan 31, 2019 reply Follow Share No, merge sort has an upper bound of $O(n \log n)$ 0 votes 0 votes balchandar reddy san commented Feb 1, 2019 reply Follow Share I think it will be θ(nlogn),O(nlogn) which is also equal to O(n^2)..it will be never be θ(n^2) 0 votes 0 votes Shubhanshu commented Feb 1, 2019 reply Follow Share Yes time complexity can be $O(n^2)$ if you use merge sort with inplace. 1 votes 1 votes sushovan commented Feb 1, 2019 reply Follow Share The time complexity of Merge sort is (nlogn) for all three cases i.e best, average and worst case. 0 votes 0 votes aambazinga commented Feb 1, 2019 reply Follow Share 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. 0 votes 0 votes Shubhanshu commented Feb 1, 2019 reply Follow Share @aambazinga in case of inplace with linked list it should take $O(n^2)$ time. Right? 0 votes 0 votes aambazinga commented Feb 1, 2019 reply Follow Share @Shubhanshu no it's O[nlogn] see this it will be clear. https://www.geeksforgeeks.org/merge-sort-for-linked-list/ 0 votes 0 votes Shubhanshu commented Feb 1, 2019 reply Follow Share Thanks. By default MS on LL is inplace only. But on array it is outplace. 0 votes 0 votes Nukku commented Sep 21, 2019 reply Follow Share What's in place and out place in merge sort? 0 votes 0 votes Please log in or register to add a comment.