merge sort

Question

given n elements merge them into one sorted list using merge procedure then what is the time complexity for this ?

explain with example

Comments

Merge procedure takes O(n)

To compare elements of two splits it will take O(n) i.e take element of one split and compare with element of other split and the process is continued for n elements

---

To merge n elements in sorted manner,  merge sort is used.  So, TC=O(nlogn)

Not O(n) because,  there are n random elements not sorted.

Answer 1

@suneetha

Time complexity of Merge Sort is O(n*Log n) in all the 3 cases (worst, average and best) as merge sort always divides the array in two halves and takes linear time to merge two halves...

 

1. https://gateoverflow.in/16103/The-time-complexity-of-producing-a-sorted-list 

 

2. https://gateoverflow.in/784/Gate-cse-2005-question-39