2

Given 4 sorted files containing 15,3,9 and 8 records what is the total number of comparisons required to merge them into a single sorted file?

Assume that we are using the merge step (from merge sort) for this.

I know that the merge step takes O(N) time to execute. But how many comparisons does it make?

2
  • thank you for your suggestions..but there are so many different answers so I am not sure which one is correct...although the exact number is hard to guess, how do you arrive at an approximate answer?
    – maxpayne
    Sep 6, 2011 at 9:11
  • You'll have to assess the reasoning of the answers yourself. I'm not certain that mine really does give the best possible worst-case, but I am sure that some of the answers give higher worst-cases than what's actually achievable (and hence are certainly wrong). The trick is to identify the error in the reasoning of each answer (including mine: if you can find one and let me know that'd be great). Sep 6, 2011 at 14:43

7 Answers 7

3

If you assume that you use the merge step from a typical merge sort, that means you can only merge 2 lists at a time, which makes things simpler. We need at least 3 merges to turn 4 lists into 1. We could split up lists, but that's throwing away information and we'll only have to merge them back eventually, so I doubt that helps (without proving it).

The only question, then, is what order to merge the lists. The worst-case number of comparisons to merge a total of k elements from two lists is k-1[*], so we want to minimize the total number of elements in all merges. I think (again, without proving it) that in this case this is done by merging pairwise from smallest to largest, that is 8+3 then 11+9 then 20+15. That's a total of 10+19+34 = 63 record comparisons in the worst case.

A less cunning choice of merges, say 15+3 then 8+9 then 18+17, would need more comparisons in the worst case (67), but you wouldn't need to know the lengths of the lists before you started.

[*] proof by induction:

With k=1, 0 comparisons are required since we have one empty list and one list of length 1.

Suppose it's true for lists of total length j (for some j >= 1). Then in the worst case, to merge two sorted lists of length j+1, we first compare the smallest elements on either side, remove the smaller one and shove it into the output list. All that remains is to merge what's left in the two lists, that is to say of total length j. We can do this in at worst j-1 comparisons by the inductive hypothesis. Hence total j+1 elements requires at worst j comparisons, which completes the induction.

0
0

Each step when need to know current smallest element among the 4 files. In other word, we need to know the smallest one of the four elements a, b, c, d. So a naive way would use three comparison for each step(a and b, c and d, the smaller of ab and cd). So the overall comparison would be 3*N (N is the total number of records).

2
  • Yes, but as soon as one file is exhausted, you only need two comparisons for each step, and when two are exhausted, only one. We do not know if and when the files will be exhausted, though.
    – Svante
    Sep 6, 2011 at 7:11
  • @Svante true. The exact number is hard to know.
    – Mu Qiao
    Sep 6, 2011 at 7:12
0

As in Mu Qiao's answer (somewhat repeated here for convenience), we can merge the lists by taking the smallest value of a, b, c, d at each step. This requires at most 3 comparisons: comparing a and b, comparing c and d and comparing the minimum of {a, b} and {c, d}. We can trivially see that this is the best we can do since 2 comparisons are insufficient.

Suppose we deplete one list. Let's assume without loss of generality that this list is d. Now to compare a, b, c we can compare a and b and then compare the minimum or {a, b} to c. We can see that we cannot do better than this since 1 comparison is insufficient.

When there are two lists, we obviously need exactly 1 comparison and when there is one list we obviously need no comparisons.

From here, we can make a worst case analysis. We can see that a larger number of non-depleted lists results in more comparisons and so, we can see that the worst case will be when the most items are processed before a list is depleted.

In this case there will be at most 14+2+8+7 = 31 comparisons before a list is depleted. From there, there will be one list depleted for each item that is processed. So we have the worst-case number of comparisons as 31*3 + 2 + 1 + 0 = 96.

2
  • 14+2+8+7 = 31 comparisons before a list is depleted ..can you explain how?
    – maxpayne
    Sep 6, 2011 at 9:15
  • @maxpayne For a list to not be depleted, it must have at least 1 item. Since your lists have 15, 2, 9 and 8 items respectively. You can remove all but 1 from each list before any of them get depleted.
    – flight
    Sep 6, 2011 at 9:18
0

If we are merging two lists, merge procedure requires at most: n1 + n2 comparisons, where n1 and n2 are the length of the lists.

With 4 lists, the total number will depend on the order we use in this merging: i.e we can merge list1 and list2 and then merge the result with list3 and then with list4; or we can merge list1 and list2, and merge list3 and list4 and then merge the 2 results.

In this case, is easy to check that this is the best strategy:

(list1 <-> list2) <-> (list3 <-> list4)          (<-> stands for merge)

Which is the maximum comparisons number? It's easy recalling the starting formula:

(15 + 3) + (9 + 8) + ((15+3) + (9+8)) = 18 + 17 + 18 + 17 = 70
12
  • How did you arrive at the conclusion that the merge procedure requires almost exactly: 2 * min(n1, n2) ?
    – maxpayne
    Sep 6, 2011 at 9:12
  • "Almost exactly"... interesting concept.
    – flight
    Sep 6, 2011 at 9:18
  • Also, this is incorrect. Merging two lists could potentially take n1+n2-1 comparisons.
    – flight
    Sep 6, 2011 at 9:27
  • i don't see how it can take more than 2*min(n1,n2), give me an example
    – Simone
    Sep 6, 2011 at 9:36
  • @Simone List 1: 1, 3, 5; List 2: 2, 4, 6 This will take 5 comparisons.
    – flight
    Sep 6, 2011 at 9:44
0

total number of comparisons required for two files of size m , n are

m + n - 1 

thus for above we require

15 + 3 -1 = 17 

8 + 9 -1 = 16

17 + 16 -1 = 32 
1
  • 1
    This question was already answered a year ago (and accepted). In such cases, it is important to explain clearly what your answer offers that isn't already included in another answer. Oct 27, 2012 at 19:30
0

The worst case in merging of 2 sorted lists occurs in the case when both the lists remain non-null for the maximum amount of time. In this case with 15, 3, 9 and 8 elements we have 3 comparisons to find the smallest element (4 elements and selection sort takes 3 comparisons). In the worst case imagine: we have 3,3,3 and 3 elements left in each list. Till this point number of comparisons are : (12 + 0 + 6 + 5)*3 = 69. Now with remaining lists of (3,3,3,3) keys reduce them to (2,2,2,2) elements ( so 4 * 3 = 12 comparisons). Again reduce (2,2,2,2) to (1,1,1,1) using 4 * 3 = 12 comparisons. Now reduce (1,1,1,1) to (0,1,1,1) by 3 comparisons. Now reduce (0,1,1,1) to (0,0,1,1) by 2 comparisons. Now reduce (0,0,1,1) to (0,0,0,1) using 1 comparison. Now add the last element to the sorted list by 0 comparisons. Hence total comparisons: 69 + 12 + 12 + 3 + 2 + 1 + 0 = 99 comparisons.

0

I think we can generalize the answer approximately. Given n lists of length k1, k2, ...,kn then in Big Oh notation the worst case is bounded by O((n-1) (k1+k2+k3...+kn)). I got this idea from doing question of CLRS (Question 2-1 of chapter 2).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.