22990atinesh
- 143
- 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
Maximum number of comparisons required to merge two sorted files
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
7 replies · 6K views
Maximum no. of comparisons required to merge two sorted files of length 'm' and 'n' is..
I think m+n-1
- 22,832
- 14,876
Please also provide the reasoning behind your attempt.22990atinesh said:
22990atinesh
- 143
- 1
@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
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
- 8,947
- 687
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
- 143
- 1
What I'm missing herercgldr said:
22990atinesh said:
- 8,947
- 687
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
- 143
- 1
rcgldr said:
rcgldr said:
Your above approach also ends up with ##m+n-1## comparisons.
- 8,947
- 687
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.