skip to content

Merging sorted log segments costs the sum of the two sizes — which merge order minimizes total cost?

level: middleimportance: should knowfreq 48%

answer

  1. Draw the merges as a binary tree
  2. Every size is re-paid at each level above it
  3. Which sizes do you want shallow?
  4. Merged results must re-enter the pool
  5. Same problem as building a code tree

basics

~10 s

Always combine the two smallest remaining segments: pull the two minima from a min-heap, add their sum to the running total, and push the result back. This is Huffman's construction wearing different clothes.

solid answer

~40 s

Repeatedly merge the **two smallest** remaining segments. Each pairwise merge costs the sum of its two inputs, so a segment's size is paid again in every merge it takes part in — meaning total cost equals the sum over original segments of size times depth in the merge tree, which is exactly Huffman's weighted path length. Take segments of 5, 8, 20 and 40 units. Smallest-first: 5+8=13, then 13+20=33, then 33+40=73, total **119**. Largest-first, the instinct to "get the big ones out of the way": 40+20=60, then 60+8=68, then 68+5=73, total **201** — 70% worse, because the 40-unit segment now rides through all three merges instead of one. The number of merges is n-1 either way; only the depths change. With a min-heap the schedule costs O(n log n).

code

pseudocode · 11 lines
pseudocode
total = 0
H = build_min_heap(sizes)
while size(H) > 1:
    a = extract_min(H)
    b = extract_min(H)
    merged = a + b
    total = total + merged
    insert(H, merged)
return total
// sizes = [5, 8, 20, 40]
// merges cost 13, then 33, then 73  ->  total = 119

go deeper

for a junior

Recognize the shape: cost equal to the sum of the two inputs means always take the two smallest. Be able to run the four-segment example by hand and reach 119.

for a middle

Explain the merge tree and the size-times-depth identity, then show why largest-first costs 201 on the same input while performing the same number of merges. Name the min-heap and the O(n log n) planning cost.

for a senior

Give the exchange argument for why smallest-first is safe, and flag the assumption it rests on: cost proportional to the sum of the inputs. Mention the two-queue O(n) route when the sizes are pre-sorted.

for a principal

Own the modelling decision. Whether smallest-first is right depends on whether per-record work or fixed per-operation overhead dominates, and getting that wrong optimizes a schedule against the wrong cost curve.

## The cost model, and why it is Huffman Given n sorted segments, only pairwise merges are available, and merging two segments of sizes a and b costs a + b (you touch every record in both). Repeat until one segment remains. Minimize the total. The merges form a binary tree: original segments are leaves, each merge an internal node holding the sum of its children. Two facts follow: - **Total cost = sum of the weights of all internal nodes.** Each merge contributes its own sum once. - Equivalently, **total cost = sum over leaves of size times depth**, because a leaf's size is re-paid in every merge above it, and the number of merges above it is its depth. That second form is the weighted path length Huffman coding minimizes, with segment sizes playing the role of symbol frequencies. So the answer is the same greedy rule: take the two smallest, replace them with their sum, repeat. ## The arithmetic that settles the argument Segments of 5, 8, 20, 40. **Two smallest each time:** 5+8 = 13 (cost 13), 13+20 = 33 (cost 33), 33+40 = 73 (cost 73). Total **119**. Check with depths: 5(3) + 8(3) + 20(2) + 40(1) = 15 + 24 + 40 + 40 = 119. **Two largest each time:** 40+20 = 60 (cost 60), 60+8 = 68 (cost 68), 68+5 = 73 (cost 73). Total **201**. Depths: 40(3) + 20(3) + 8(2) + 5(1) = 120 + 60 + 16 + 5 = 201. Both schedules perform exactly three merges and produce the same final 73-unit segment. The difference is entirely which sizes sit deep. Merging the largest pair first maximizes the depth of the heaviest leaves — precisely the wrong end of the objective. A subtler trap: "sort ascending, then keep merging the accumulator with the next segment." On 5, 8, 20, 40 this happens to give 119, because the running sum stays below the next segment. Change the sizes to four equal segments of 1 and it breaks: accumulating gives 2 + 3 + 4 = 9, while the greedy rule gives 2 + 2 + 4 = 8. Sorting once is not enough; **merged results must re-enter the candidate pool**, which is what the heap is for. ## Why merging the two smallest is safe The standard exchange argument runs in two steps. First, in *some* optimal merge tree the two smallest segments are **sibling leaves at maximum depth**. Take an optimal tree; its deepest internal node has two leaf children (if either child were internal, deeper leaves would exist). Suppose one of those deepest siblings is a segment of size L while a smaller segment of size S sits shallower, at depth d(S) < d(L). Swapping them changes the total by (S - L)(d(L) - d(S)), and with S <= L and d(L) >= d(S) that quantity is at most zero — the swap never makes the tree worse. Do it for both smallest segments and you have an optimal tree in which they are deepest siblings. Second, induct. Once the two smallest are siblings, their parent's weight is their sum, and the rest of the tree treats that parent as a single leaf of that combined size. So the original problem on n segments reduces to the same problem on n-1, with the two smallest replaced by their sum, plus a fixed additive cost of that sum. The greedy first move is therefore consistent with *an* optimal solution, and the induction carries it to the end. Note what the argument does **not** claim: that the greedy tree is the *only* optimal one, or that the two smallest must be siblings in *every* optimal tree. It claims that there exists an optimal tree in which they are — which is exactly enough to license the move. ## Cost of computing the schedule With a min-heap: one build, then n-1 rounds of two extractions and one insertion, so **O(n log n)** time and O(n) space. Note the distinction between the cost of *planning* the merges and the total merge cost itself, which is the number you were asked to minimize; interviewers sometimes conflate them. If the sizes arrive already sorted, you can drop to **O(n)** with two queues and no heap at all: one queue holds the original sizes in ascending order, the other holds merged results, which are themselves produced in non-decreasing order. At each step take the two smallest heads across the two queues, and enqueue the sum onto the merged queue. Each element is enqueued and dequeued once. ## Where the model stops applying The rule depends entirely on cost being the *sum of the two inputs*. If per-merge overhead dominates — a fixed setup cost per operation rather than a per-record cost — the objective changes and merging fewer, larger pairs can win. State the cost model before defending the schedule; a candidate who applies the greedy rule without checking that assumption is pattern-matching, not reasoning.

  • Why is merging the two smallest a safe first move?
    Because some optimal merge tree has them as sibling leaves at maximum depth. Take any optimal tree; if a large segment sits deeper than a smaller one, swapping the two changes the cost by (smaller minus larger) times (deeper minus shallower depth), which is at most zero. So the swap never hurts. Replacing that sibling pair with their sum then reduces the problem to n-1 segments, and induction finishes the argument.
  • The sizes already arrive sorted — can you beat O(n log n)?
    Yes, O(n) with two queues and no heap. One queue holds the original sizes ascending; the other collects merged results, which come out in non-decreasing order. Each step takes the two smallest heads across both queues and enqueues their sum onto the merged queue. Every element is enqueued and dequeued exactly once. Note this is the cost of planning the schedule, not the merge cost being minimized.
  • When would you not use this greedy rule for a real merge job?
    When the cost model is different. The rule assumes each merge costs the sum of its inputs, so a segment is re-paid once per level above it. If a fixed per-operation overhead dominates the per-record work, the objective shifts toward doing fewer, larger merges, and the smallest-first schedule can lose. Establish the cost model first; the greedy rule is a consequence of it, not a universal truth about merging.

It is the reverse of packing a moving truck: whatever you load first gets carried through every later trip, so the heaviest box should be the last thing you pick up.

saying these in an interview costs you the question

  • Merges the largest pair first to get them out of the way
  • Claims total cost is the same in any merge order
  • Sorts once and merges left to right without reinserting results
  • Confuses the O(n log n) planning cost with the merge cost itself
  • Applies the greedy rule without stating the per-merge cost model

context

resolving links…