You are not logged in. Please login at www.codechef.com to post your questions!

×

# How merge sort work ?

 2 Please explain how merge sort work and calculate the time complexity of merge sort. asked 10 Nov '16, 22:58 2★rashedcs 497●6●17●56 accept rate: 4%

 0 Check This Link Visual Algo Check this Link answered 11 Nov '16, 01:57 1.1k●13 accept rate: 20%
 2 Merge sort can be precisely described by a tree of height = ( log2(n) + 1 ) for an array of size n. Consider the diagram. If we manage to ensure the work done at each level of the tree is O(n) then the total work would be of the order n*(height of the tree). So that would be O(nlog(n)). This is where the merge subroutine comes into the picture.The argument we make is that work done to merge to sorted arrays is O(n). And hence at each level total work = (total subproblems)*(work for each subproblem).If we assume the above statement to be true. I wont go into the details of merge subroutine.But subproblems at each level = 2^(level) if root is at level 0. Work to solve a subproblem = size of subprobem = n/2^(level) Total work at each level = (2^(level)) * (n/2^(level)) = n Total work in all levels = Total work at each level * (Total number of levels) = n*( log2(n) + 1 ) = O(nlogn) answered 10 Jun '17, 23:39 4★atul1910 31●2 accept rate: 0%
 1 answered 11 Nov '16, 00:22 53●1●5 accept rate: 0%
 1 Pls take a look at merge sort tutorial here. answered 08 Dec '18, 14:28 0★millie09 11●1 accept rate: 0%
 0 can you please explain me how to create a call recording app like this answered 11 Nov '16, 00:56 1 accept rate: 0%
 0 The University of Seville (US) continues to climb positions Mathway | Problem Solver in the QS ranking, something that is reflected in the data of the latest report of the QS World University Rankings 2017 by subject, where the Seville is located among the 500 best universities in the world in 19 disciplines, occupying four of them put in the range 151-200. answered 10 Jun '17, 12:52 0★leemate 1 accept rate: 0%
 0 As far as complexity is concerned, it's NlogN in all cases. answered 10 Jun '17, 17:02 419●2●10 accept rate: 7%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×846

question asked: 10 Nov '16, 22:58

question was seen: 810 times

last updated: 08 Dec '18, 14:28