CODEWITHSUNDEEP
algorithmsortingmergesort
Bhaskar
Bhaskar

Reputation: 89

Basic Confusion on MERGE SORT’s DIVIDE step

In Merge Sort, the running time of Divide step for every element is considered theta(1) i.e constant time in CLRS.

My confusion is : Let divide is an elementary operation and which takes constant time C1. Now, Consider the pesudocode
enter image description here

Now, When MERGE-SORT function called for the first time then it will take C1 to divide the input (Note:- We are not considering Time taken by Merge function) And this MERGE-SORT will divide the input lg(n) time ( or we can say it will call itself lg((n)) times ) So the total time taken in dividing inputs should be C1 * lg(n) that is theta(lg(n)).

But In CLRS : enter image description here

If we consider that then Divide Step will require theta(1) time ( as whole)

NOTE: lg is log to the base 2

P.S. - Sorry in advance because my English is not upto that mark. Edits are welcome :)

Upvotes: 0

Views: 654

Answers (2)

saketk21
saketk21

Reputation: 465

The basic understanding of Merge Sort is as such - Consider we have two halves of an array which are already sorted. We can merge these two halves in O(n) time.

Mathematically speaking, the function Merge Sort calls itself twice for two of its halves (The DIVIDE step), and then merges these two (The CONQUER step).

Recurrence Relation

Now, if we solve this recurrence relation (by using appropriate mathematical analysis), we get the relation as follows:

Solution to Recurrence

This clearly indicates that the DIVIDE step that takes O(1) time is called n times, while the total merging workload of merging all the smaller halves of various sizes is O(n logn), which is the upper limit. Hence the complexity of O(n logn) (Thanks to Yves Daoust for this clarification).

However, the DIVIDE step takes O(1) time only, which is called O(n) times. Thus, the workload for division is O(n).

Upvotes: 1

user1196549
user1196549

Reputation:

One step of division indeed takes constant time O(1).

But contrary to your thinking, there are Θ(N) divisions in total (1+2+4+8+...N/2).

Anyway this is not accounted for as the total merging workload is Θ(N Log N).

Upvotes: 1

Related Questions