Modified merge Sort Algorithm

Question

Describe a modified merge sort algorithm, in which a given sequence is split into split into three sub-sequences of equal size approximately one-third. Analyze asymptotically the time complexity of your algorithm. How to solve this?

See Master Theorem.

irrelephant
– irrelephant

2012-11-12 04:55:59 +00:00
Commented Nov 12, 2012 at 4:55 — irrelephant
– irrelephant, Commented Nov 12, 2012 at 4:55
@user1817250: What have you already tried?

Patricia Shanahan
– Patricia Shanahan

2012-11-12 04:58:36 +00:00
Commented Nov 12, 2012 at 4:58 — Patricia Shanahan
– Patricia Shanahan, Commented Nov 12, 2012 at 4:58

rknife · Accepted Answer · 2012-12-26 13:59:49Z

1

This is probably your homework but i would recommend that you do read chapter 2 from Cormen , Lierson and Rivest .

solve this recurrence relation - T(n) = 3T(n/3) + O(n)

Every problem is subdivided into 3 sub-problems and contain n/3 part of the original data. Apply masters theorem to it and you will find that the answer is 0( n*log(n) ).

Note - here logarithm is of base 3 .

answered Dec 26, 2012 at 13:59

rknife

3002 silver badges15 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Modified merge Sort Algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related