eguruchela

What is the time complexity of merge sort


he elements are divided into partitions until each partition has sorted elements. Then these partitions are merged and the elements are properly positioned to get a fully sorted list

It is a recursive algorithm and time complexity can be expressed as following recurrence relation.

T(n) = 2T(n/2) + O(n), The solution of the recurrence is O(nLogn).

The list of size N is divided into a max of Logn parts and the merging of all sublists into a single list takes O(N) time.

The worst-case run time of this algorithm is O(nLogn)

Best-Case Time Complexity: O(n*log n)

Worst-Case Time Complexity: O(n*log n)

Average-Case Time Complexity: O(n*log n)

👈       👉