Optimal Merge Pattern is the greedy topic examiners love because its rule takes one line to state and one careless step to get wrong. Five of the ten questions below are previous-year problems, from GATE, ISRO, UGC NET and a Wipro paper, and between them they repeat the same three traps: stopping at the cost of the final merge, forgetting to reinsert a merged file into the sorted pool, and reporting record movements when the question asked for comparisons. Attempt each question before reading its explanation, and keep the Algorithms learn module open for the surrounding greedy theory.
The greedy rule in one line
Merging files of sizes m and n costs m + n record movements because every record moves once. Since a merged file may move again later, the total depends on the order. Always merge the two currently smallest files so that large files pass through fewer merges. This builds the same kind of binary merge tree used in Huffman coding, a useful connection when practising Binary Tree MCQs.
Q1. Choose the correct greedy step
In the optimal merge pattern problem, we select:
(a) The smallest two arrays and merge them
(b) The largest two arrays and merge them
(c) Any two arrays and merge them
(d) The smallest and largest arrays and merge them
Answer: (a). Choosing the two smallest arrays keeps large arrays out of early merges, so their elements are copied fewer times. Largest-first does the opposite and increases repeated copying.
The classic four-file merge, fully worked
Q2. Find the minimum retrieval time
The four C-Programs of the following lengths are to be stored in a hard disk of infinite length: (l₁, l₂, l₃, l₄) = (5, 10, 8, 25). The minimum retrieval time of all four programs is ___?
(a) 32
(b) 64
(c) 84
(d) 128
Answer: (c) 84. First sort the pool: 5, 8, 10, 25.
Merge
5 + 8 = 13. New pool:10, 13, 25.Merge
10 + 13 = 23. New pool:23, 25.Merge
23 + 25 = 48.Total cost:
13 + 23 + 48 = 84.
The final merge alone costs 48, so option (a) 32 cannot be right. The larger wrong options miss that a record is counted again every time its file takes part in a further merge, which is exactly what the sorted-pool order minimises.
GATE's five-file record-movement classic
Q3. Minimum record movements, GATE CS 1999
The minimum number of record movements required to merge five files A (with 10 records), B (with 20 records), C (with 15 records), D (with 5 records), and E (with 25 records) is:
(a) 165
(b) 90
(c) 75
(d) 65
Answer: (a) 165. Sort the pool first: 5, 10, 15, 20, 25.
5 + 10 = 15, giving15, 15, 20, 25.15 + 15 = 30, giving20, 25, 30.20 + 25 = 45, giving30, 45.30 + 45 = 75.
The total is 15 + 30 + 45 + 75 = 165. Option (c), 75, is the tempting mistake because it is only the final merge cost. This question and the other previous-year ones are also worked through in the Optimal Merge Pattern PYQ set.
The comparisons twist: m + n - 1
The worst-case number of comparisons while merging sorted sequences of lengths m and n is m + n - 1, not m + n. Across an optimal merge tree, subtract one for each merge from the record-movement total.
Q4. Worst-case comparisons, GATE CS 2014 Set 2
Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.
Answer: 358. These are the optimal merges, shown the same way on the solved GATE 2014 question page:
20 + 24 = 44, costing 43 comparisons.30 + 35 = 65, costing 64 comparisons.44 + 50 = 94, costing 93 comparisons.65 + 94 = 159, costing 158 comparisons.
Therefore, 43 + 64 + 93 + 158 = 358. As a check, merge sizes total 44 + 65 + 94 + 159 = 362; four merges mean 362 - 4 = 358 comparisons.
Q5. The Wipro 2024 MCQ twin
The stem and sequence lengths are the same as Q4. The options are:
(a) 500
(b) 358
(c) 450
(d) 259
Answer: (b) 358. The working is exactly Q4's, so the only decision left is which quantity is being asked for: 362 would be the record-movement total, while 358 is the worst-case comparison count.
Bigger pools, same discipline
With larger pools, rewrite the sorted pool after every merge so each new file stays in the correct position.
Q6. Six-file optimal merge
Given an array F = {10, 5, 100, 60, 25, 11}, assume the array content F[i] indicates the length of the iᵗʰ file and we want to merge all these files into one single file. Find the total number of record moves in the optimal solution.
Answer: 414. Starting pool: 5, 10, 11, 25, 60, 100.
5 + 10 = 15, pool11, 15, 25, 60, 100.11 + 15 = 26, pool25, 26, 60, 100.25 + 26 = 51, pool51, 60, 100.51 + 60 = 111, pool100, 111.100 + 111 = 211.
Total: 15 + 26 + 51 + 111 + 211 = 414.
Q7. Eight-file optimal merge
Given a set of 8 files from F₁ to F₈ with the following number of pages, find the minimum number of record movements required to merge them into a single file:
File | F₁ | F₂ | F₃ | F₄ | F₅ | F₆ | F₇ | F₈ |
|---|---|---|---|---|---|---|---|---|
Pages | 18 | 3 | 15 | 12 | 10 | 11 | 7 | 9 |
Answer: 247. Sort to 3, 7, 9, 10, 11, 12, 15, 18, then track the running total:
3 + 7 = 10, total 10.9 + 10 = 19, total 29.10 + 11 = 21, total 50.12 + 15 = 27, total 77.18 + 19 = 37, total 114.21 + 27 = 48, total 162.37 + 48 = 85, total 247.
Eight files require seven merges. The common error is forgetting to reinsert each new size into the sorted pool.
Merge cost equals weighted external path length
The total merge cost also equals the weighted external path length of the merge tree: Σ(file size × leaf depth). This identity explains why optimal merging and Huffman construction use the same greedy algorithm.
Q8. Compare x and y
A binary tree stores the files a = 20, b = 30, c = 10, d = 5 and e = 30 at its leaves, with d and c at depth 3 and a, b and e at depth 2. Its weighted external path length is x, and the minimum total record movements needed to merge those same five files into one sorted file is y. Then x - y is ____.
Answer: 0. Compute y through merging:
5 + 10 = 15, pool15, 20, 30, 30.15 + 20 = 35, pool30, 30, 35.30 + 30 = 60, pool35, 60.35 + 60 = 95.
Thus, y = 15 + 35 + 60 + 95 = 205.
Now compute x from the leaf depths given in the stem:
x = 5(3) + 10(3) + 20(2) + 30(2) + 30(2)
x = 15 + 30 + 40 + 60 + 60 = 205
Therefore, x - y = 205 - 205 = 0.
The storage-ordering cousins: smallest file first
Sequential-storage questions use the same smallest-first instinct, but there is no pairwise merging. Sort smaller files first to reduce scan distance, a connection to the Sorting Algorithms comparison.
Q9. Equal-frequency files, ISRO Computer Science 2015
Six files F₁, F₂, F₃, F₄, F₅, and F₆ have 100, 200, 50, 80, 120, and 150 records respectively. In what order should they be stored so as to optimize access time? Assume each file is accessed with the same frequency.
(a) F₃, F₄, F₁, F₅, F₆, F₂
(b) F₂, F₆, F₅, F₁, F₄, F₃
(c) F₁, F₂, F₃, F₄, F₅, F₆
(d) Ordering is immaterial as all files are accessed with the same frequency.
Answer: (a). Sorting ascending gives F₃(50), F₄(80), F₁(100), F₅(120), F₆(150), F₂(200). Equal access frequency removes weighting between files, but placement still changes the scan distance.
Q10. Sequential-device order, UGC NET Paper 2 November 2017
Suppose there are six files F₁, F₂, F₃, F₄, F₅, F₆ with corresponding sizes 150 KB, 225 KB, 75 KB, 60 KB, 275 KB, and 65 KB respectively. The files are to be stored on a sequential device in such a way that optimizes access time. In what order should the files be stored?
(a) F₅, F₂, F₁, F₃, F₆, F₄
(b) F₄, F₆, F₃, F₁, F₂, F₅
(c) F₁, F₂, F₃, F₄, F₅, F₆
(d) F₆, F₅, F₄, F₃, F₂, F₁
Answer: (b). Ascending order gives F₄(60), F₆(65), F₃(75), F₁(150), F₂(225), F₅(275). Option (a) is the exact descending order, the designed mirror trap.
The short version and your next step
Merging sizes
mandncostsm + nrecord movements.Always merge the two smallest current files, then reinsert the result into the sorted pool.
Worst-case comparisons cost
m + n - 1per merge, so subtract the number of merges from the record-movement total.Total merge cost equals the weighted external path length of the merge tree.
Sequential-storage ordering also puts smaller files first, but it is a different model.
The five previous-year questions above are solved in full inside GATE Guidance by Sanchit Sir. For the rest of the syllabus, browse the wider GATE CS preparation options, and keep drilling the sorted-pool habit until reinserting each merged file is automatic.
