1,105,581 Community Members

Mergesort Analysis

Member Avatar
jim_underpants
Newbie Poster
4 posts since Dec 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

Assume that we have a mergesort algorithm which takes 2 series as an input and returns 1 after the merge each time. So that if we want to count say memory blocks we would need 2 blocks for the input and 1 for the output accordingly, total size of 3 blocks (3B). My question is whether this algorithm could run if the memory size is 2B + O(1)?

Member Avatar
Rashakil Fol
Super Senior Demiposter
2,596 posts since Jun 2005
Reputation Points: 982 [?]
Q&As Helped to Solve: 209 [?]
Skill Endorsements: 42 [?]
Team Colleague
 
0
 

Uh, what? What is a "block"? Also the output of mergesort is as big as the input, it's not half as big the way you say.

Member Avatar
jim_underpants
Newbie Poster
4 posts since Dec 2011
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]
 
0
 

A block is a set of data that i retract from the hard drive. A block could have 2 or more sorted elements, lets say numbers. So a block could be something like: [2 5 8] or [3 9 10 12]. Before we start the merging every block has the same size. You are right the algorithm is not mergesort itself, but a version of mergesort that combines the 2 series from the input to 1 at the output, as I described above. It follows the same rules as mergesort though, that's why I said mergesort, because I thought that we need to take its recursive definitions and recurrence relations to solve the problem.

Member Avatar
Rashakil Fol
Super Senior Demiposter
2,596 posts since Jun 2005
Reputation Points: 982 [?]
Q&As Helped to Solve: 209 [?]
Skill Endorsements: 42 [?]
Team Colleague
 
0
 

Okay but what I meant was the the output of merging is as big as the input. So if you measure the output as being 1B you're going to have a nonsensical measurement.

You
This article has been dead for over three months: Start a new discussion instead
Post:
Start New Discussion
View similar articles that have also been tagged: