Optimal merge pattern; when greedy fails

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Huffman cost equals the sum of what? from Lesson 4.2.3
• Job sequencing: which slot for each job? from Lesson 4.2.2
• Merging lists of sizes p and q costs? from Lesson 3.2.1

1 · The Hook

🎣

Five sorted files must be merged into one, two at a time, and each merge costs the total size of the two files. The order matters: merging big files early makes their records move again and again. The cheapest order is Huffman's rule again. And some tempting greedy rules fail completely; GATE expects you to recognise which.

2 · Predict First

🤔

Files of sizes 20, 30, 10, 5, 30 records. Always merge the two smallest. What is the total cost (records moved)?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

5 + 10 = 15; 15 + 20 = 35; 30 + 30 = 60; 35 + 60 = 95. Total 15 + 35 + 60 + 95 = 205.

Optimal merge pattern

Merging two sorted files of sizes a and b costs a + b. To merge n files into one with minimum total cost, repeatedly merge the two smallest (a min-heap): exactly Huffman's algorithm, with sizes as frequencies. Total cost = sum of merge sizes = Σ size × (number of merges it takes part in).

Where greedy fails

Greedy coin change is optimal for "canonical" systems such as {1, 2, 5, 10, 20, 50, 100} (Indian rupees, US coins), but not for arbitrary coin sets. The general problems need dynamic programming (Phase 5).

Greedy algorithms still to come

Kruskal's and Prim's MST algorithms and Dijkstra's shortest paths (Phase 6) are greedy, each with its own correctness proof.

4 · Visual

Optimal merge of 20, 30, 10, 5, 30 (merge the two smallest each time)

  5 + 10 -> 15
 15 + 20 -> 35
 30 + 30 -> 60
 35 + 60 -> 95          total cost = 15 + 35 + 60 + 95 = 205

5 · Worked Examples

Example 1 Easy

Optimal merge cost of files of sizes 2, 3, 5, 7, 11, 13?

Solution

5, 10, 17, 24, 41 → 97.

Example 2 Medium

Coins {1, 3, 4}, amount 6: how many coins does largest-first use, and what is the minimum?

Solution

Greedy 4 + 1 + 1 = 3; optimal 3 + 3 = 2.

Example 3 GATE

Why does the optimal merge pattern use a min-heap?

Solution

To extract the two smallest sizes and insert their sum in O(log n) each: total Θ(n log n).

6 · GATE Traps

⚠️

• Merge cost counts the merged sizes at every step, not the final size once.
• Largest-coin-first is optimal only for canonical coin systems.
• Optimal merge = Huffman with sizes as frequencies.
• A greedy rule that works on examples still needs a proof.

7 · Memory Hook

🧠

"Small with small first; and check greedy before trusting it."

8 · Connect the Dots

Phase 4 is complete: divide and conquer and greedy. When greedy fails (0/1 knapsack, coin change) and subproblems overlap, the tool is dynamic programming, Phase 5.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksOptimal merge

Optimal total cost of merging sorted files of sizes 20, 30, 10, 5, 30?

Numerical answer: ________

Q2NAT2 marksMerge pattern

Optimal total cost of merging files of sizes 8, 4, 6, 12?

Numerical answer: ________

Q3NAT1 markGreedy coins

Coins {1, 5, 6, 9}, amount 11: how many coins does largest-coin-first use?

Numerical answer: ________

Q4NAT1 markOptimal coins

Coins {1, 5, 6, 9}, amount 11: minimum number of coins?

Numerical answer: ________

Q5MSQ2 marksGreedy correctness

For which problems is a greedy algorithm optimal?

• (A) Activity selection by earliest finish
• (B) Huffman coding
• (C) Fractional knapsack
• (D) 0/1 knapsack

10 · Rule Card

• Optimal merge: repeatedly merge the two smallest (min-heap); cost = Σ merges; = Huffman.
• Greedy fails: 0/1 knapsack, coin change with non-canonical coins, shortest-first activities, nearest-neighbour paths.
• Canonical coin systems: greedy works.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

optimal merge patternmerge costnon-canonical coin systemsgreedy counterexamplescanonical coin systems

12 · Answer Vault