Mergesort Analysis

[jim_underpants]

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)?

[Rashakil Fol]

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]

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]

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.