# Maximum number of comparisons required to merge two sorted files

Tags:
1. Jan 6, 2015

### 22990atinesh

1. The problem statement, all variables and given/known data
Maximum no. of comparisons required to merge two sorted files of length 'm' and 'n' is..

2. Relevant equations

3. The attempt at a solution
I think m+n-1

2. Jan 6, 2015

### Orodruin

Staff Emeritus

3. Jan 6, 2015

### 22990atinesh

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

4. Jan 6, 2015

### 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.

5. Jan 7, 2015

### 22990atinesh

What I'm missing here

6. Jan 7, 2015

### 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?

7. Jan 10, 2015

### 22990atinesh

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

8. Jan 11, 2015

### 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.