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

×

How merge sort work ?

Please explain how merge sort work and calculate the time complexity of merge sort.

asked 10 Nov '16, 22:58

rashedcs's gravatar image

2★rashedcs
49761756
accept rate: 4%


link

answered 11 Nov '16, 01:57

neilit1992's gravatar image

3★neilit1992
1.1k13
accept rate: 20%

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)

alt text

link

answered 10 Jun '17, 23:39

atul1910's gravatar image

4★atul1910
312
accept rate: 0%

edited 10 Jun '17, 23:43

link

answered 11 Nov '16, 00:22

shahadatcs's gravatar image

0★shahadatcs
5315
accept rate: 0%

Pls take a look at merge sort tutorial here.

link

answered 08 Dec '18, 14:28

millie09's gravatar image

0★millie09
111
accept rate: 0%

can you please explain me how to create a call recording app like this

link

answered 11 Nov '16, 00:56

sohail12345's gravatar image

0★sohail12345
1
accept rate: 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.

link

answered 10 Jun '17, 12:52

leemate's gravatar image

0★leemate
1
accept rate: 0%

As far as complexity is concerned, it's NlogN in all cases.

link

answered 10 Jun '17, 17:02

godslayer12's gravatar image

1★godslayer12
419210
accept rate: 7%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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