Member Avatar for 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)?

  • 2 Contributors
  • 3 Replies
  • 226 Views
  • 4 Days Discussion Span
  • Latest Post Latest Post by Rashakil Fol

Dani AI

Generated

Short answer: under the standard external‑memory (streaming block) model, you cannot do the usual two‑way streaming merge in linear I/O with only 2B + O(1) memory — you need three block buffers (one for each input run and one for output). That is the simplest, correct rule to use when analysing mergesort by block counts.

Why: a streaming merge must hold the current head(s) of both runs and accumulate output until you can write a full block. With only two blocks you can either (a) keep both input heads but then have nowhere to buffer block‑aligned output, forcing element‑by‑element writes (lots of extra I/O), or (b) reuse one input block as output space and risk overwriting unread input. Both options break the usual I/O cost guarantees. This is what was getting at when noting the output size equals the sum of inputs — you cannot treat the output as magically smaller.

Workarounds and tradeoffs: in RAM (contiguous array) there are in‑place merge algorithms that use O(1) extra words; they are nontrivial to implement and often slower or more complex than the standard buffered merge. In an external/disk setting you can do in‑place/block‑rotation merges that reuse freed input blocks as output, but they incur extra block moves, seeks and implementation complexity — so you trade extra I/O/time for lower memory. Stable, simple, I/O‑optimal merging is normally implemented with 3 buffers.

Practical recommendation: for asymptotic analysis and for simple, high‑performance code assume 3B. If you are constrained to 2B+O(1), be explicit which concessions you accept (extra passes, extra seeks, unstable merge, or a complex in‑place algorithm) and pick an algorithm designed for that tradeoff rather than trying to rework the standard streaming merge. , that will guide whether your mergesort variant is feasible under your memory bound.

Recommended Answers

All 3 Replies

Member Avatar for 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.

Member Avatar for 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.

Edited by jim_underpants because: n/a
Member Avatar for 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.

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.