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)?
jim_underpants
0
Newbie Poster
Recommended Answers
Jump to PostUh, 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.
All 3 Replies
Rashakil Fol
978
Super Senior Demiposter
Team Colleague
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.
jim_underpants
0
Newbie Poster
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.
Rashakil Fol
978
Super Senior Demiposter
Team Colleague
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.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.