- #1
- 142
- 1
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
Please also provide the reasoning behind your attempt.I think m+n-1
What I'm missing hereAn 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.
@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
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?