Register

Merge Sort Doubt

1,731 views

3 Answers

0 0 votes
First merge sort for half array(1to m) that takes T(n/2)

Second merge sort for last half array(m+1to n)

Final phase merging them in O(n) time

So total time complexity=2T(n/2)+O(n/2)

=O(nlogn)
0 0 votes
T(n) =2T(n/2) + O(n)

T(1) = 1

Because in mergesort function we call two time mergesort and at last

we call merge procedure , merge procedure take O(n) and each time we

divide array in half .
Voting & Accepting an answer helps improve the community
← Previous · SubnettingNext → · Transport layer, dat...
← Previous in category · Self-doubt - Case of...Next in category → · ace test 4
Position:
Show:

Related questions

3 3 votes
1 1 answer
283
283 views
GO Classes asked Aug 4
283 views
GO Classes DPP | GATE CS, DA | Algorithms | Merge Sort
Assume that a merge sort algorithm in the worst case takes $30$ seconds for an input of size $64$. Which of the following most closely approximates the maximum input size...
2 2 votes
1 1 answer
195
195 views
GO Classes asked Aug 4
195 views
GO Classes DPP | GATE CS, DA | Algorithms | Four-Way Merge Sort
Suppose instead of dividing the input into two parts, a modified merge sort divides the input into four equal parts, sorts each one-fourth recursively, and finally combin...
3 3 votes
1 1 answer
223
223 views
GO Classes asked Aug 4
223 views
GO Classes DPP | GATE CS, DA | Algorithms | Merge Sort
Merge sort divides an array of size $n$ into two halves, recursively sorts both halves, and then merges the two sorted halves.Which recurrence correctly represents merge ...
1 1 vote
1 1 answer
2.2k
2.2k views
rahul sharma 5 asked Mar 9, 2018
2,194 views
Merge sort algorithm
Consider the modified merge sort where we divide array into 5 equal sub arrays instead if 2(as in standard merge sort).What is the time complexity if modified merge sort?...