Maximum number of comparisons required to merge two sorted files

[22990atinesh]

Homework Statement

Maximum no. of comparisons required to merge two sorted files of length 'm' and 'n' is..

Homework Equations

The Attempt at a Solution

I think m+n-1

 

[Orodruin]

I think m+n-1

Please also provide the reasoning behind your attempt.

 

[22990atinesh]

@Orodruin Please see this question

Suppose we have two list LIST-1 & LIST-2 of sorted integers of size 3, 2 respectively (say)

1. First we compare $1^{st}$ element of the both list and suppose we get minimum value from LIST-1, So we store it in the new array. Now we are having two lists of size 2, 2 (1 Comparison)
2. Now we compare $2^{nd}$ element of LIST-1 with $1^{st}$ element of LIST-2 this time element from LIST-2 becomes minimum, So we store it . Now we are having two list of size 2, 1 (1 Comparison)
3. Now we compare $2^{nd}$ element of LIST-1 with $2^{nd}$ element of LIST-2 this time element from LIST-1 becomes minimum, So we store it . Now we are having two list of size 1, 1 (1 Comparison)
4. Now we compare $3^{rd}$ element of LIST-1 with $2^{nd}$ element of LIST-2 this time element from LIST-2 becomes minimum. so we store it . Now we are having two list of size 1, 0 (1 Comparison)
5. Now we store last element left from LIST-1 to the array. Hence 3+2-1 = 4 comparisons

 

[rcgldr]

An alternative, list-m and list-n. Assume all but the last element of list-m is smaller than the first element of list-n, that's m-1 comparisons (not including the compare with last element of list-m yet). Assume last element of list-m is greater than all of the elements in list-n, that's n comparisons, and the last element of list-m is copied to the output list, 0 comparisons. The issue is proving there isn't a pattern that produces more compares.

 

[22990atinesh]

An alternative, list-m and list-n. Assume all but the last element of list-m is smaller than the first element of list-n, that's m-1 comparisons (not including the compare with last element of list-m yet). Assume last element of list-m is greater than all of the elements in list-n, that's n comparisons, and the last element of list-m is copied to the output list, 0 comparisons. The issue is proving there isn't a pattern that produces more compares.

What I'm missing here

@Orodruin Please see this question
Suppose we have two list LIST-1 & LIST-2 of sorted integers of size 3, 2 respectively (say)

1. First we compare $1^{st}$ element of the both list and suppose we get minimum value from LIST-1, So we store it in the new array. Now we are having two lists of size 2, 2 (1 Comparison)
2. Now we compare $2^{nd}$ element of LIST-1 with $1^{st}$ element of LIST-2 this time element from LIST-2 becomes minimum, So we store it . Now we are having two list of size 2, 1 (1 Comparison)
3. Now we compare $2^{nd}$ element of LIST-1 with $2^{nd}$ element of LIST-2 this time element from LIST-1 becomes minimum, So we store it . Now we are having two list of size 1, 1 (1 Comparison)
4. Now we compare $3^{rd}$ element of LIST-1 with $2^{nd}$ element of LIST-2 this time element from LIST-2 becomes minimum. so we store it . Now we are having two list of size 1, 0 (1 Comparison)
5. Now we store last element left from LIST-1 to the array. Hence 3+2-1 = 4 comparisons

 

[rcgldr]

You're not missing anything. The issue here is how do you prove the worst case number of comparasons without going through every possible scenario?

 

[22990atinesh]

An alternative, list-m and list-n. Assume all but the last element of list-m is smaller than the first element of list-n, that's m-1 comparisons (not including the compare with last element of list-m yet). Assume last element of list-m is greater than all of the elements in list-n, that's n comparisons, and the last element of list-m is copied to the output list, 0 comparisons. The issue is proving there isn't a pattern that produces more compares.

You're not missing anything. The issue here is how do you prove the worst case number of comparasons without going through every possible scenario?

Your above approach also ends up with $m+n-1$ comparisons.

 

[rcgldr]

A logical explanation rather than specific cases would be a better "proof". After each compare, one element is moved from either list-m or list-n. In the worst case scenario, there is 1 element remaining in list-m and 1 element remaining in list-n, and m+n-2 compares have been performed. There is one more compare performed, which moves an element from either list-m or list-n, emptying that list, so the remaining element from the other list is moved without doing any compares, and the worst case scenario is m+n-1 compares.